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.

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.

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

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012

3

posted

0

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.

subject: Interview Question: Finding min difference