CareerCup

I guess the arrays are sorted. In that case, the problem is same as selecting one element from each of n arrays such that (max element - min element) is minimized. If total # of element in n arrays is m, then using a min heap it can be solved in O(m logn).

y is there so much unnecessary discussion for a simple problem.
Below code is easy to trace so not presenting algo.
The code assumes that array are sorted.

#include <stdio.h>
#define ABSDIFF(a,b) (((a)>(b))?((a)-(b)):((b)-(a)))
void findMinDst (int* pArray1, int* pArray2, int* pArray3, int size1, int size2, int size3)
{
	int min=(1<<30),curMin=0;
	int i=0,j=0,k=0;
	int index1=0,index2=0,index3=0;
	while((i<size3)&&(i<size2)&&(k<size3))
	{
		curMin=ABSDIFF(pArray1[i],pArray2[j])+
			   ABSDIFF(pArray2[j],pArray3[k])+
			   ABSDIFF(pArray3[k],pArray1[i]);
		if(min>curMin)
		{
			min=curMin;
			index1=i;
			index2=j;
			index3=k;
		}
		if((pArray1[i]<pArray2[j])&&(pArray1[i]<pArray3[k]))
		{
			i++;
		}
		else if((pArray2[j]<pArray1[i])&&(pArray2[j]<pArray3[k]))
		{
			j++;
		}
		else
		{
			k++;
		}
	}
	printf("Min Dist:[%d]\n", min);
	printf("Elements:[%d][%d][%d]", pArray1[index1],pArray2[index2],pArray3[index3]);
}
int main()
{
	int A[] = {4, 10, 15, 20};
	int B[] = {1, 13, 29};
	int C[] = {5, 14, 28};
	findMinDst(A,B,C,sizeof(A)/sizeof(int),sizeof(A)/sizeof(int),sizeof(A)/sizeof(int));
	return 0;
}

Let we've 4 arrays, and the solution is {a,b,c,d}. Let, a >= b >= c >= d. 
Now, the expression for sum of the difference = abs(a-b) + abs(b-c) + abs(c-d) + abs(d-a). 
We can write it as = (a-b) + (b-c) + (c-d) + (a-d). 
First 3 components equates to (a-d). 
Hence, the expression becomes 2*(a-d).

Hope this helps to understand how the two problems are related.

Is the arrays have to be sorted ?

@buried.shopno: your comment doesnt really help anything. If possible, can you please elaborate more?

@buried.shopno: your comment doesnt really help anything. If possible, can you please elaborate more?

Well, I think it needs clarification (from original poster) if we really needs NC2 differences, or N differences. I'd work, and let know if find some efficient way for the NC2 differences.

what if?
Let's merge all arrays into single one, with marking items. Merge sort will do that.

The next step would be to run thru big array finding minimal window (not sure about correct problem name). This is actually is O(sum(lengths)) hard.

The proof: suppose we found a solution with min = m0, lets prove that we need to move left pointer - by examining movement of right pointer instead we'd increase max(differences) => we need bla bla bla... seems pretty clear i think.

So, what about the problem is exactly? Seems it has 2 variations - one answered by buried, how about the other variation? Which question was asked in the interview?

@Anonymous Finding window with minimum sum would not work as there's no assumption as to what elements come from what array. I.e. your window may be the whole array.

If we cannot make an assumption about a >= b >= c >= d, and we must find minimum elements for each pair of arrays as stated, I can think of something like:

Assuming arrays are sorted:
1. for each required pair do the merge keeping track of which element came from which array (simple bitmap would do that). This is O(n+m)
2. In one pass compare adjacent elements, making sure they are from different arrays, if not -> next, while comparing keep track of minimum and element indexes. This step is O(n)

3. Repeat for each pair.

Another idea is to use BST, but it is somewhat more complicated...

As the problem statement does not say "sum of pairwise differences", rather mentioned "sum of their differences" - it implies buried.shopno's approach is right here.

You could model the problem as a graph and use Djikstra's algorithm, but the fact that you have to go back to the same number in A means that you have to replicate the nodes of B and C |A| times.. which actually wouldn't be difficult with some light bookkeeping. You would only have to know which edge is outgoing from the selected C node, given the choice of node in A..

Here's the solution. It assumes that:
if
|a-b| + |b-c| + |c-a| ==> min and |x| >= 0,
then
|a-b| is min of possible |A[i]-B[j]|, |b-c| is min of possible |B[i]-C[j]|, |c-a| is min of possible |C[i]-A[j]|

Solution itself:
Sort arrays if they aren't. Find best |a1[i]-a2[j]| value for each pair of arrays. In the original example they would be:
A (15)-->B (13)
B (13)-->C (14) AND B(29)-->C(28)
C (14)-->A (15)

We can verify if we found a "chain" of values, but for clarity let's omit this (it needs research whether it would save time, but it can) step.

Now we have 4 chains starts:
Chain 1) A(15)->B(13) which we should continue, finding appropriate minimum distance from B(13) till array C - will be 14 and then from C(14) till A automatically will be 15 because chain starts at it.
Chain 2) B(13)->C(14). Continue: C(14)->A(15) and then automatically to chain start at B(13)
Chain 3) B(29)-->C(28). COntinue: C(28)->A(20) and then automatically to chain start at B(29)
Chain 4) C(14)->A(15). Coninute: A(15)->B(13) and then automatically to chain start at C(14)

Now calculate results for 3 chains:
Chains 1), 2) and 4) result is 3
Chain 3) result is 18

Now choose the best chains (there can be several with the same sum) and filter out duplicates if you didn't do this after finding best distances between array pairs.

If I estimated correctly, algorithm is of O(n^2) speed, where n is max array length (if number of arrays is relatively small).

Actually my initial algorithm is wrong (though the assumption regarding f(x,y,z) is correct). Correct one is (it is also of O(n^2)):
For each value in A:
1) Find best entry in B.
2) Build chain B->C...->A finding best entry in each next array and automatically making closure to A arrays in the last one
3) Choose best chain

In our example:
A = {4, 10, 15, 20}
B = {1, 13, 29}
C = {5, 14, 28}

For values in A find best entries in B:
1) 4-1-5-4, value 8
2) 10-13-14-10, value 8
3) 15-13-14-15, value 3
4) 20-29-28-20, value 18
Choose the best variant: 3)

@anonymous: you are simply an idiot! Who had asked you to post code here for others? Learn first how to solve a problem "accurately" and "efficiently". There are many smart people here on careercup, who don't come here to spoon feed others; rather enrich themselves & help others sharing and getting knowledge. you stupid asshole just keep your mouth shut up. And next time, before posting a solution, read (and again read) the problem. Solve the problem for yourself first. If you can't solve it, ask for help. If you can (i doubt), give your idea. Everyone should be able to code - when the idea is properly grasped.

is it nC2 pairs or n pairs??
can any of above 41 posts tell me??

My IDEA is that better we can write a program like:

min = find_min(Array a,b) + find_min(Array b,c) + find_array(c,a)

Write the function like:
find_min(a,sizeofA,b,sizeofB)
{
here find the min of a and b;
retrun it;
}

I hope this helps :)

#include<stdio.h>
#include<math.h>
void minsum(int a[],int b[],int c[],int x,int y,int z){
int i,j,k,i1,j1,k1,max,max1;
max=((abs(a[0]-b[0]))+(abs(b[0]-c[0]))+(abs(c[0]-a[0])));
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
{
for(k=0;k<z;k++)
{
max1=((abs(a[i]-b[j]))+(abs(b[j]-c[k]))+(abs(c[k]-a[i])));
if(max1<max)
{
max=max1;
i1=i;
j1=j;
k1=k;
}
}
}
}
printf("%d %d %d",a[i1],b[j1],c[k1]);
}
void main(){
int a[]={4,10,15,20};
int b[]={1,13,29};
int c[]={5,14,28};
minsum(a,b,c,4,3,3);
}

Assuming arrays are sorted
1) Initialize i,j an k to 0. i, j and k are indices for the three arrays
2) find the sum of differences of elements at indices i, j and k. If this is smaller than current minimum, update current minimum
3) Find the smallest of the elements present at index i, j, k and increment that index if you are not going out of bound
4) Goto step 2, until all three arrays are exhausted
5) Return stored minimum

public class CoverWithMinimumWindowSize {

	protected static class Element implements Comparator<Element>{
		int value;
		int listIndex;
		int positionInList;
		
		Element(){
			
		}
		
		Element(int value, int listIndex,int positionInList){
			this.value = value;
			this.listIndex = listIndex;
			this.positionInList = positionInList;
		}
		
		public int compare(Element e1, Element e2){
			return e1.value-e2.value;
		}
	}
	
	public static int findCoverWithMinimumWindowSize(List<int[]> lists) throws Exception{
		int numLists = lists.size();
		
		if(numLists == 1){
			throw new Exception("Only one list");
		}
		
		int index[] = new int[numLists];
		int listSize[] = new int[numLists];
		for(int i = 0; i < numLists; i++){
			int[] listi = lists.get(i);
			Arrays.sort(listi);
			listSize[i] = listi.length;
			if(listSize[i] == 0){
				throw new Exception("Empty list " + i);
			}
		}
		
		boolean done=false;
		Arrays.fill(index, 0);
		
		int windowStart,windowEnd;
		PriorityQueue<Element> minHeap = new PriorityQueue<Element>(numLists,new Element(0,0,0));
		PriorityQueue<Element> maxHeap = new PriorityQueue<Element>(numLists,Collections.reverseOrder(new Element(0,0,0)));
		for(int i = 0; i < numLists; i++){
			int[] listi = lists.get(i);
			Element elem = new Element(listi[0],i,0);
			minHeap.add(elem);
			maxHeap.add(elem);
		}
		
		Element minElement = minHeap.peek();
		Element maxElement = maxHeap.peek();
		int maxWindowSize = -1;
		
		while(!done){
			minElement = minHeap.peek();
			windowStart = minElement.value;
			int minElementSource = minElement.listIndex;
			int positionInList = minElement.positionInList;
			
			maxElement = maxHeap.peek();
			windowEnd = maxElement.value;
			int windowSize=windowEnd-windowStart;
			if(maxWindowSize == -1){
				maxWindowSize = windowSize;
			} else if(windowSize < maxWindowSize){
				maxWindowSize = windowSize;
			}
			
			minHeap.poll();
			maxHeap.remove(minElement);
			
			if(positionInList+1 < listSize[minElementSource]){
				int[] listi = lists.get(minElementSource);
				int value = listi[positionInList+1];
				Element elem = new Element(value,minElementSource,positionInList+1);
				minHeap.add(elem);
				maxHeap.add(elem);
				positionInList++;
			} else {
				done = true;
			}
		}

		return maxWindowSize;
	}
	
	public static void main(String[] args) throws Exception{
		int list1[] = {4, 10, 15, 20};
		int list2[] = {1, 13, 29};
		int list3[] = {5, 14, 28};

		List<int[]> testcase = new LinkedList<int[]>();
		testcase.add(list1);
		testcase.add(list2);
		testcase.add(list3);
				
		int result = findCoverWithMinimumWindowSize(testcase);
		
		System.out.println(result);
	}
}

1) Find the avg of combined array(i.e (4+10+15+20+1+13..+29)/10 = 13.9)
2) Using binary search find two elements from each array,1st element larger than avg ,2nd element smaller than average.
3) so at max we ll need to find the "min" of combination of the above 2+2+2 numbers
So complexity ll be O(n) i.e for finding avg.

Correct me if am wrong .