# Interview Question: Finding min difference

posted 4 years ago

This is the question someone asked at stackoverflow. I tried to understand its solution but wasnt able to. Seems like I am missing something.

Can someone help me in understanding it.

Suggested Solution:

Link

Given an N arrays of size K each.. each of these K elements in the N arrays are sorted, each of these N*K elements are unique. Choose a single element from each of the N arrays, from the chosen subset of N elements. Subtract the minimum and maximum element. Now, this difference should be least possible Minimum.. Hope the problem is clear

Sample:

N=3, K=3

N=1 : 6, 16, 67

N=2 : 11,17,68

N=3 : 10, 15, 100

here if 16, 17, 15 are chosen.. we get the minimum difference as 17-15=2

This is the question someone asked at stackoverflow. I tried to understand its solution but wasnt able to. Seems like I am missing something.

Can someone help me in understanding it.

Suggested Solution:

Link

My Blog SCJP 5 SCWCD 5

posted 4 years ago

Can you write it in some sentences so that it becomes easy to understand that what are you doing. Also did you analyze its time complexity?

My Blog SCJP 5 SCWCD 5

Ryan McGuire

Ranch Hand

Posts: 1055

4

posted 4 years ago

If I understand correctly, in the original example it was just a coincidence that the element pulled from each array was at the same position.

For instance, if...

N1 = (15, 33, 55)

N2 = (1, 4, 17)

N3 = (9, 16, 200)

The answer would still be (15, 17, 16) for a minimum difference of 2.

Is that right, Himanshu?

Himanshu Gupta wrote:Can you write it in some sentences so that it becomes easy to understand that what are you doing. Also did you analyze its time complexity?

If I understand correctly, in the original example it was just a coincidence that the element pulled from each array was at the same position.

For instance, if...

N1 = (15, 33, 55)

N2 = (1, 4, 17)

N3 = (9, 16, 200)

The answer would still be (15, 17, 16) for a minimum difference of 2.

Is that right, Himanshu?

posted 4 years ago

ya right. The difference of the selected items (max-min) should be minimum.

My Blog SCJP 5 SCWCD 5

Ryan McGuire

Ranch Hand

Posts: 1055

4

posted 4 years ago

Is this still an open question? The recent activity at stackoverflow has gone into some more detail to describe the idea behind the solution, including some modifications.