# Interview Question: Finding min difference

Himanshu Gupta
Ranch Hand
Posts: 598
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:

Ranch Hand
Posts: 312
My attempt as follows.

Himanshu Gupta
Ranch Hand
Posts: 598
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?

Ryan McGuire
Ranch Hand
Posts: 1078
4
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?

Himanshu Gupta
Ranch Hand
Posts: 598
ya right. The difference of the selected items (max-min) should be minimum.

Ryan McGuire
Ranch Hand
Posts: 1078
4
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.