Interview Question: Finding min difference

[Himanshu Gupta]

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

int count[N] = { 0 }
int head = 0;
int diffcnt = 0;
// mindiff is initialized to overall maximum value - overall minimum value
int mindiff = combined_val[N * K - 1] - combined_val[0];
for (int i = 0; i < N * K; i++) 
{
  count[combined_ind[i]]++;

  if (count[combined_ind[i]] == 1) {
    // diffcnt counts how many arrays have at least one element between
    // indexes of "head" and "i". Once diffcnt reaches N it will stay N and
    // not increase anymore
    diffcnt++;
  } else {
    while (count[combined_ind[head]] > 1) {// WHY ARE WE COMPARING IT WITH 1?
      // We try to move head index as forward as possible while keeping diffcnt constant.
      // i.e. if count[combined_ind[head]] is 1, then if we would move head forward
      // diffcnt would decrease, that is something we dont want to do.
      count[combined_ind[head]]--;
      head++;
    }
  }

  if (diffcnt == N) {
    // i.e. we got at least one element from all arrays
    if (combined_val[i] - combined_val[head] < mindiff) {
      mindiff = combined_val[i] - combined_val[head];
      // if you want to save actual numbers too, you can save this (i.e. i and head
      // and then extract data from that)
    }
  }
}

[Madhan Sundararajan Devaki]

My attempt as follows.

import java.io.Console;
import java.util.Arrays;

public class MDFView
{
	public static final int RADIX = 10,
		MINIMUM_VALUE = 1;

	public MDFView()
	{
		monitor = System.console();
		if(null == monitor)
		{
			throw new IllegalStateException("INVALID STATE:Console");
		}
	}
	
	public int getNumberOfArrays()
	{
		return getIntValue(this.monitor, "Enter the number of arrays      : ");
	}
	
	public int getSizeOfArrays()
	{
		return getIntValue(this.monitor, "Enter the size of arrays        : ");
	}
	
	public int getLocation()
	{
		return getIntValue(this.monitor, "Enter the location in the array : ");
	}
	
	public int[] getArray(int argSize)
	{
		if(MINIMUM_VALUE > argSize)
		{
			throw new IllegalArgumentException("INVALID ARGUMENT:argSize");
		}
		int[] arrayOfNumbers = new int[argSize];

		for(int i = 0; i < argSize; i++)
		{
			arrayOfNumbers[i] = getIntValue(this.monitor, 
				"Enter array element " + (i+MINIMUM_VALUE) + " of " + argSize + 
				" ");
		}
		Arrays.sort(arrayOfNumbers);

		return arrayOfNumbers;
	}
	
	private int getIntValue(Console argConsole, String argMessage)
	{
		boolean retry = false;
		int value = 0;
		
		do
		{
			try
			{
				retry = false;
				value = Integer.parseInt(argConsole.readLine(argMessage), RADIX);
			}
			catch(NumberFormatException nfe)
			{
				retry = true;
			}
		} while(retry);

		return value;
	}
	
	private Console monitor = null;
}

import java.util.Arrays;

public class MDFModel
{
	public MDFModel(int[][] argTwoDimensionMatrix)
	{
		if((null == argTwoDimensionMatrix) || (0 == argTwoDimensionMatrix.length))
		{
			throw new IllegalArgumentException("INVALID ARGUMENT:argTwoDimensionMatrix");
		}
		this.twoDimensionMatrix = argTwoDimensionMatrix;
	}
	
	public int[] getSelectedNumbers(int argLocation)
	{
		if(0 > argLocation)
		{
			throw new IllegalArgumentException("INVALID ARGUMENT[0]:argLocation");
		}
		if(argLocation > this.twoDimensionMatrix[0].length)
		{
			throw new IllegalArgumentException("INVALID ARGUMENT[1]:argLocation");
		}
		int[] selectedNumbers = new int[this.twoDimensionMatrix.length];
		int index = 0;
		
		for(int i = 0; i < this.twoDimensionMatrix.length; i++)
		{
			selectedNumbers[index] = this.twoDimensionMatrix[i][argLocation];
			index++;
		}
		Arrays.sort(selectedNumbers);
		
		return selectedNumbers;
	}

	private int[][] twoDimensionMatrix = null;
}

public class MDFController
{
	public static void main(String[] args)
	{
		// Get Input
		MDFView view = new MDFView();
		int numberOfArrays = view.getNumberOfArrays();
		int sizeOfArrays = view.getSizeOfArrays();
		int location = view.getLocation();
		int[][] twoDimensionMatrix = new int[numberOfArrays][sizeOfArrays];
		
		for(int i = 0; i < numberOfArrays; i++)
		{
			twoDimensionMatrix[i] = view.getArray(sizeOfArrays);
		}
		view = null;

		// Extract selected numbers
		MDFModel model = new MDFModel(twoDimensionMatrix);
		int[] selectedNumbers = model.getSelectedNumbers(location-1);
		model = null;
		
		// Compute Minimum Difference
		int minimumDifference = selectedNumbers[selectedNumbers.length-1] - selectedNumbers[0];
		System.out.print(selectedNumbers[selectedNumbers.length-1]);
		System.out.print(" - ");
		System.out.print(selectedNumbers[0]);
		System.out.print(" = ");
		System.out.println(minimumDifference);
	}
}

// NOTE : Time complexity not analysed
// RESULTS
Enter the number of arrays      : 3
Enter the size of arrays        : 3
Enter the location in the array : 2
Enter array element 1 of 3 6
Enter array element 2 of 3 16
Enter array element 3 of 3 67
Enter array element 1 of 3 11
Enter array element 2 of 3 17
Enter array element 3 of 3 68
Enter array element 1 of 3 10
Enter array element 2 of 3 15
Enter array element 3 of 3 100
17 - 15 = 2

[Himanshu Gupta]

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]

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]

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

[Ryan McGuire]

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.