Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
68
of 76 vote

There are k lists of sorted integers. Make a min heap of size k containing 1 element from each list. Keep track of min and max element and calculate the range.
In min heap, minimum element is at top. Delete the minimum element and another element instead of that from the same list to which minimum element belong. Repeat the process till any one of the k list gets empty.
Keep track of minimum range.

For eg.
List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]

Min heap of size 3. containing 1 element of each list
Heap [0, 4, 5]
Range - 6

Remove 0 and add 9
Heap [4, 9, 5]
Range - 6

Remove 4 and add 10
Heap [5, 9, 10]
Range - 6

and so on....

Finally you will yield the result.

- aasshishh April 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

nice solution

- DashDash April 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
9
of 13 votes

since the input lists are already sorted, we should take advantage of it rather than creating a new minHeap.

- Vin April 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 votes

can you please tell me how you are keep an account of minimum range in this. How you are going to find out which range is minimum because you going forward without keeping the record of range.
for instance: If you are taking an array for tracking the records then each time you have to find the smallest element of the array and you have to compare it with current result and so on .... till you are getting minimum.
I m taking array here only for explanation, for that you can use a heap also. but any how you have to provide extra code to keep track for ranges to find minimum range and the proper possession of each and ever combination with range, for that you require another data structure.

- Md Husain April 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 votes

When you are creating the heap for the first time, make a separate variable that keeps track of max number in the heap. Everytime you add a new element into the heap, check the new element against this variable. That way you can get the max-min range

- bob dole April 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

Nice solution only one thing is missing which is how to make use of sorted nature of lists as rightly pointed by @Vinod K

- aka April 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice idea!!!I have implemented it quickly. @Vinod K @aka, What do you mean "how to make use of sorted nature of lists" ?

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define MAX_LIST_LEN 256
#define MAX_K 128

struct LinkNode{
	int _data;
	struct LinkNode *_next;
};

struct MinHeap{
	struct LinkNode *_min_heap[MAX_K+1];
	int _k;
	int _max;
};

void MinHeapInit(MinHeap &MH) {
	MH._k = 0;
}

void MinHeapPush(MinHeap &MH, struct LinkNode *node) {
	MH._k++;	
	int parent;
	int cur = MH._k;
	MH._min_heap[cur] = node;

	while( parent = cur / 2 ) {
		if (node->_data >= MH._min_heap[parent]->_data) {
			break;
		}
		MH._min_heap[cur] = MH._min_heap[parent];
		cur = parent;
	}
	MH._min_heap[cur] = node;
	return;	
}


void MinHeapAdjust(MinHeap &MH) {
	if (MH._k < 1) {
		return;
	}
	int cur = 1;
	struct LinkNode *cur_node = MH._min_heap[1];

	while (cur*2 <= MH._k) {
		int left = cur*2;
		int right = left + 1;
		int min = left;
		if (right <= MH._k && MH._min_heap[left]->_data >= MH._min_heap[right]->_data) {
			min = right;
		}
		if (MH._min_heap[cur]->_data > MH._min_heap[min]->_data) {
			MH._min_heap[cur] = MH._min_heap[min];
			cur = min;
		} else
			break;
	}
	MH._min_heap[cur] = cur_node;
}

void MinRangeOfKList(struct LinkNode *lists[MAX_K], int k) {
	struct MinHeap mh;
	if (k < 1) {
		return;
	}
	MinHeapInit(mh);
	// init min heap
	int max = lists[0]->_data;
	int min_range;
	for (int i = 0; i < k ;i++) {
		assert(lists[i]);
		MinHeapPush(mh, lists[i]);
		if (lists[i]->_data > max) {
			max = lists[i]->_data;
		}
	}
	mh._max = max;
	min_range = max - mh._min_heap[1]->_data;

	// loop pop 
	struct LinkNode *node;
	int range;
	while (node = mh._min_heap[1]->_next) {
		mh._min_heap[1] = node;
		if (node->_data > mh._max)
			mh._max = node->_data;
		MinHeapAdjust(mh);
		range = mh._max - mh._min_heap[1]->_data;
		if (min_range > range) {
			min_range = range;
			max = mh._max;
		}
	}	
	printf("minimum range is [%d,%d]\n", max - min_range, max);
}

int main(int argc, char *argv[]) {
	const int K = 1;
	struct LinkNode *lists[K];
	for (int i = 0; i < K; i++) {
		struct LinkNode **ptr = &lists[i];
		int N;
		while (scanf("%d", &N)) {
			if (N == -1) break;
			*ptr = (struct LinkNode *)malloc(sizeof(LinkNode));
			(*ptr)->_data = N;
			ptr = &(*ptr)->_next;
			*ptr = NULL;
		}
	}
	MinRangeOfKList(lists, K);
	for (int i = 0; i < K; i++) {
		struct LinkNode *cur = lists[i];
		struct LinkNode *saved = cur;
		while (cur) {
			saved = cur->_next;
			free(cur);
			cur = saved;
		}
	}
	return 0;
}

- persistentsnail April 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How can we prove the correctness of this algorithm? What if we remove the element from the heap which has next minimum value, instead of removing the minumum value itself? Which one would be correct? Both, or none?

- Nawaz April 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That a good idea. I also wrote the code.
It will be better to use vectors instead of array in real applications.

struct pn
{
    int n; /* belong to which array */
    int d; /* the data value */
    pn(int _n, int _d) { n = _n; d = _d; }
    pn(const pn& _pn) { n = _pn.n; d = _pn.d; }
};

inline void swap(pn& a, pn& b) { pn c = a; a = b; b = c; }

void adjust(int n, pn a[])
{
    int i = 0, max = 0;
    int l = 0, r = 0;
    for(i = n / 2; i >= 0; i--)
    {
        max = i;
        l = 2 * i + 1;
        r = 2 * i + 2;
        if(l < n && a[l].d > a[max].d) { max = l; }
        if(r < n && a[r].d > a[max].d) { max = r; }
        if(max != i) { swap(a[max], a[i]); }
    }
}

void heapsort(int n, pn a[])
{
    int i = 0;
    adjust(n, a);
    for(i = n - 1; i > 0; i--)
    {
        swap(a[0], a[i]);
        adjust(i, a);
    }
}

int main()
{
    int i = 0, j = 0;
    const int m = 3;
    const int n = 5;
    int ms = 0, me = 0;
    int ts = 0, te = 0;
    int a[m][n] = { {4, 10, 15, 24, 26}, {0, 9, 12, 20, 35}, {5, 18, 22, 30, 50} };
    int cur[m] = {1, 1, 1}; /* record the current positions of each array which haven't been used */
    pn heap[m] = {pn(0, a[0][0]), pn(1, a[1][0]), pn(2, a[2][0])};

    heapsort(m, heap);
    ms = heap[0].d;
    me = heap[m - 1].d;
    while(true)
    {
        heapsort(m, heap);
        ts = heap[0].d;
        te = heap[m - 1].d;
        /* if the current range is smaller than the minimum range */
        if(te - ts < me - ms) { ms = ts; me = te; }

        /* if the sub-array which the smallest element comes from hasn't to the end */
        if(cur[heap[0].n] != n)
        {
            heap[0].d = a[heap[0].n][cur[heap[0].n]];
            cur[heap[0].n] += 1;
        }
        else
        {
            break;
        }
    }
    cout << ms << endl;
    cout << me << endl;
    return 0;
}

- Gabriel May 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

It does use the sorted feature of K lists. If you try to prove the correctness of this algorithm, it does depend on the properties that "each element in the list is in increasing order"

- Hao June 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

what is the time complexity of this algorithm?

- nondescript October 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 votes

This is based on a problem in CLRS. Read heap chapter, there is a problem that talks about how to sort k sorted lists. This problem is just extension of that.

Here java code,

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.SortedSet;
import java.util.TreeSet;

public class GoogleProblem {

	public static void main(String[] args) {

		List<List<Integer>> lists = new ArrayList<List<Integer>>();
		List<Integer> list1 = new ArrayList<Integer>();
		list1.add(4);
		list1.add(10);
		list1.add(15);
		list1.add(24);
		list1.add(26);
		List<Integer> list2 = new ArrayList<Integer>();
		list2.add(0);
		list2.add(9);
		list2.add(12);
		list2.add(20);
		List<Integer> list3 = new ArrayList<Integer>();
		list3.add(5);
		list3.add(18);
		list3.add(22);
		list3.add(30);

		lists.add(list1);
		lists.add(list2);
		lists.add(list3);

		Result result = findCoveringRange(lists);
		System.out.println(result.startRange + ", " + result.endRange);
	}

	public static Result findCoveringRange(List<List<Integer>> lists) {
		Result result = null;

		int start = -1, end = -1;
		int rDiff = Integer.MAX_VALUE;
		int k = lists.size();

		PriorityQueue<Data> pQueue = new PriorityQueue<Data>();
		SortedSet<Data> entries = new TreeSet<Data>();
		Map<Integer, Data> listNoAndEntry = new HashMap<Integer, Data>();

		for (int i = 0; i < k; i++)
			pQueue.add(new Data(lists.get(i).remove(0), i));

		while (!pQueue.isEmpty()) {
			Data minData = pQueue.remove();
			if (lists.get(minData.listNo).size() > 0)
				pQueue.add(new Data(lists.get(minData.listNo).remove(0),
						minData.listNo));

			if (listNoAndEntry.size() == k) {

				Data first = entries.first();
				if ((entries.last().data - first.data) + 1 < rDiff) {
					start = first.data;
					end = entries.last().data;
				}
				entries.remove(first);
				listNoAndEntry.remove(first.listNo);
			}

			if (listNoAndEntry.containsKey(minData.listNo))
				entries.remove(listNoAndEntry.remove(minData.listNo));

			listNoAndEntry.put(minData.listNo, minData);
			entries.add(minData);
		}

		if (listNoAndEntry.size() == k) {

			Data first = entries.first();
			if ((entries.last().data - first.data) + 1 < rDiff) {
				start = first.data;
				end = entries.last().data;
			}
			entries.remove(first);
			listNoAndEntry.remove(first.listNo);
		}

		result = new Result(start, end);
		return result;
	}

}

class Result {
	public final int startRange, endRange;

	public Result(int startRange, int endRange) {
		this.startRange = startRange;
		this.endRange = endRange;
	}
}

class Data implements Comparable<Data> {
	public final int data;
	public final int listNo;

	public Data(int data, int listNo) {
		this.data = data;
		this.listNo = listNo;
	}

	@Override
	public int compareTo(Data o) {
		// TODO Auto-generated method stub
		return data - o.data;
	}
}

- sankarmail December 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This is how I reason about this solution.

Think of drawing points from k lists on a X axis line. We first consider
the minimum point from all lists. Lets assume it is from list A. For any
range involved this point, the minimum range is the range involving the
other k-1 points, each of which is the minimum of the other k-1
different lists. Let use R to indicate this range. So the minimum range
involving all k lists is among R and the minimum range involving the k-1
lists and list A with the minimum removed. Repeat this process until one
of k lists is empty.

- yaojingguo December 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

aasshishh's solution in Python:

def minRange(lll):
import heapq
heap = []
num_elts = 0
for k in range(0,len(lll)):
li = lll[k]
if len(li)==0:
print 'none of the lists can be empty'
return 0
num_elts += len(li)
heapq.heappush(heap,(li[0],k))
oldrangemin = min(heap)[0]
oldrangemax = max(heap)[0]
oldheaprange = oldrangemax - oldrangemin
for i in range(0,num_elts):
heap_min_elt = heapq.heappop(heap)
k = heap_min_elt[1]
heap_new_elt = lll[k].pop(0)
heapq.heappush(heap, (heap_new_elt,k))
rangemin = min(heap)[0]
rangemax = max(heap)[0]
newheaprange = rangemax - rangemin
if newheaprange < oldheaprange:
oldheaprange = newheaprange
oldrangemin = rangemin
oldrangemax = rangemax
if len(lll[k])==0:
break
return [oldrangemin, oldrangemax]

>>>my_list_of_lists = [[2,50,60],[10,20,40],[2,3,100],[4,5,6]]
>>>minRange(my_list_of_lists)
>>>[2, 10]

- pythonuser March 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

This is the same as: merge all the N lists into one long array, then keep a sliding window of N.

- axx06xx April 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here's my Python version of that. heapq.merge should be better than heappush, taking advantage of the already sorted lists.

import heapq

def find_minimum_range(sequences):
	# Maintain information which sequence each item belongs to
	sequences = [[(item, n) for item in seq] for n, seq in enumerate(sequences)]
	# Merge sequences into a single minheap, taking advantage of already sorted lists
	heap = heapq.merge(*sequences)
	# Current items to test
	found_range = None
	last_range = None
	current_items = [None] * len(sequences)
	for item, n in heap:
		current_items[n] = item
		if not all(current_items): # List not yet filled
			continue
		# Find range of current selection
		minimum = min(current_items)
		maximum = max(current_items)
		current_range = abs(maximum-minimum)
		# Update minimum range
		if not last_range or current_range < last_range:
			found_range = [minimum, maximum]
			last_range = current_range
	
	return found_range

- quitereasonably May 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if the min or max appears multiple time.
Say k = 6
current heap is 2 2 2 6 6 6
And a new element say 3 is replacing 2 in 1st list. Getting min is not an issue as its a minheap an still we will get 2 as a minm.

What if i replace last 6 with 5 ?
I feel that somewhere we need to maintain the counts of elements in the heap.

- Anonymous August 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good solution, here's my implementation (visual 2013, boost 1.57)

namespace
{
    inline std::queue<unsigned, std::deque<unsigned>>  vectorToSortedQueue( std::vector< unsigned >& v )
    {
        BOOST_REQUIRE(!v.empty());
        std::sort(std::begin(v), std::end(v));
        return std::queue<unsigned, std::deque<unsigned>>(std::deque<unsigned>(std::begin(v), std::end(v)));
    }

    std::pair< unsigned, unsigned >    getMinMaxValues(const std::vector<std::queue<unsigned, std::deque<unsigned>>>& queues, unsigned& posMinElement)
    {
        std::pair< unsigned, unsigned > minMaxValues(UINT_MAX, 0);
        auto f = [&](unsigned pos, unsigned value)
        {
            if ((minMaxValues.first = std::min(minMaxValues.first, value)) == value)
                posMinElement = pos;
            minMaxValues.second = std::max(minMaxValues.second, value);
        };
        for ( unsigned i = 0; i < queues.size(); ++i )
            f(i, queues[i].front());

        return minMaxValues;
    }

    // dequeue smallest element
    inline bool    iterate(std::vector<std::queue<unsigned, std::deque<unsigned>>>& queues, unsigned currentMinPos)
    {
        queues[currentMinPos].pop();
        return !queues[currentMinPos].empty();
    }

    template <typename... Ts>
    std::pair< unsigned, unsigned >    getSmallestRange( Ts&... vectors )
    {
        BOOST_REQUIRE( sizeof...(Ts) > 0 );
        std::vector< std::queue<unsigned, std::deque<unsigned>> > sortedQueues{ vectorToSortedQueue(vectors)... };

        std::pair< unsigned, unsigned > smallestRange;
        auto minDiff = UINT_MAX;
        unsigned currentMinPos;
        do
        {
            auto currentRange = getMinMaxValues(sortedQueues, currentMinPos);
            if (currentRange.second - currentRange.first < minDiff)
            {
                minDiff = currentRange.second - currentRange.first;
                smallestRange = currentRange;
            }
        } while (iterate(sortedQueues, currentMinPos));

        return smallestRange;
    }
}

// You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.
BOOST_AUTO_TEST_CASE( SmallestRangeTestSuite )
{
    std::vector<unsigned> v1{ 4, 10, 15, 24, 26 };
    std::vector<unsigned> v2{ 0, 9, 12, 20 };
    std::vector<unsigned> v3{ 5, 18, 22, 30 };

    auto result = getSmallestRange(v1, v2, v3);
    // The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3
    BOOST_CHECK(result.first == 20 && result.second == 24);
}

- Stephane Molina January 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We don't need a heap here...

#include <stdio.h>

int getsize(int* r) {
  if (r[0] <= r[1]) {
    if (r[2] <= r[0]) return r[1]-r[2];
    else if (r[2] <= r[1]) return r[1]-r[0];
    return r[2]-r[0];
  }
  if (r[2] <= r[1]) return r[0]-r[2];
  else if (r[2] <= r[0]) return r[0]-r[1];
  return r[2]-r[1];
}

int main(void) {
  int a[] = { 0, 9, 12, 20 };
  int b[] = { 4, 10, 15, 24, 26 };
  int c[] = { 5, 18, 22, 30 };
  int la = 4, lb = 5, lc = 4;
  int minrange[3] = { a[0], b[0], c[0] };
  int minsize = getsize(minrange);
  int ia = 1, ib = 1, ic = 1;
  int currrange[3] = { a[0], b[0], c[0] };
  while (ia < la || ib < lb || ic < lc) {
    int x = 1000;
    int xid = -1;
    if (ia < la) { x = a[ia]; xid = 0; }
    if (ib < lb && b[ib] < x) { x = b[ib]; xid = 1; }
    if (ic < lc && c[ic] < x) { x = c[ic]; xid = 2; }
    currrange[xid] = x;
    int currsize = getsize(currrange);
    if (currsize < minsize) {
      minrange[0] = currrange[0];
      minrange[1] = currrange[1];
      minrange[2] = currrange[2];
      minsize = currsize;
    }
    if (xid == 0) ia++;
    else if (xid == 1) ib++;
    else ic++;
  }
  printf("%d %d %d\n", minrange[0], minrange[1], minrange[2]);
  printf("%d\n", minsize);
  return 0;
}

- song May 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
16
of 30 vote

This can be solved easily as below.
1. initialize smallest_range as MAX_INT
2. keep 3 pointers/index p1, p2 and p3 which points to the first elements of lists L1, L2 and L3 respectively.
3. find the max value and min value pointed/indexed by p1, p2 and p3
4. difference of max value and min value discovered in step 3 is the current range. compare it with smallest_range and update it, if found smaller.
5. increment the pointer/index of min value found in step 3.
6. repeat step 3 to 5 until the pointer/index of min value is in range.

constant space and O(n) time.

- Vin April 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

Correct....
no doubt sol is fantastic..... I like the way of presenting your sol.... great job...

- PKT April 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include<iostream>
#include<cmath>
#include<climits>
using namespace std;

int findRange(int p1,int p2, int p3)
{
	return max(max(abs(p1-p2),abs(p2-p3)),abs(p3-p1));
}


int** findMin( int **p1,int **p2,int **p3)
{
	int **m = p1;
    if (**m > **p2) m = p2;
    if (**m > **p3) return p3;
    return m;
}



int main()
{
	int a[]={4, 10, 15, 24, 26,-1};
	int b[]={0, 9, 12, 20,-1};
	int c[]={5, 18, 22, 30,-1};
	int i=0;
	int *p1=a,*p2=b,*p3=c;
	int min=INT_MAX;
	int **t;
	while((*p1 != -1)&&(*p2!=-1)&&(*p3!=-1))
	{

		int(findRange(*p1,*p2,*p3)<min);
		min=findRange(*p1,*p2,*p3);
		t=findMin(&p1,&p2,&p3);
		
		(*t)++;
		

	}
	(*t)--;
	cout<<*p1<<"'"<<*p2<<"'"<<*p3<<"'"<<min<<endl;
	
	return 0;
}

- yogi.rulzz April 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

It is actually O(N*k) time with O(1) space.

Step 3: find the max value and min value pointed/indexed by p1, p2 and p3, will have O(k) time execution every time.

It is a nice solution!

- xint April 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@xint - time will be O(n) only.

I had taken an example of 3 lists above. we can generalize it.

Instead of 3 pointers, take an array of K pointers which initially points to the first elements of K lists.
Now find the minValue and maxValue among this K pointers.
Find the range and update smallest_range, if needed.
Increment the pointer points to minValue and compare the value now pointed with minValue and maxValue and update it, if needed. so this will take only constant time.(no need to find the minValue and maxValue among K pointers each time since we are already tracking min and max among the K pointers )
repeat till end of list

time - O(n), space - O(k)

- Vin April 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

your code stop when one list reach the end, right? But in some case, the optimal solution need to look through all elements in every list. Let me know if I am wrong.

- TA April 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I mean yogi.rulzz's code

- TA April 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh, I think I know the problem. Once one of the list reach the end, other list's elems will always greater than current ones. Hence the min_range will not be affected.
Sorry for the misunderstanding.

- TA April 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

plz read the question again, it asks k lists.
solution becomes O(nk)

- mh May 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

List 1: [1, 2, 3, 80]
List 2: [1, 2, 3, 90, 200]
List 2: [1, 2, 3, 99, 300]
I think your approach doesn't work for this.

- prity June 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your runtime in the comment above is completely wrong.

"so this will take only constant time.(no need to find the minValue and maxValue among K pointers each time since we are already tracking min and max among the K pointers ) "

Every time you move a pointer you are removing minValue and replacing it wiht the new element. Therefore since the previous minValue is "removed" (because you moved the pointer), to find the NEW minvalue, you need to go through all k pointers in the list to see what the new minValue is, which is NOT necessarily the value at your current pointer you just moved. you need to go through and compare again, therefore @xint is correct.

- nphardon August 10, 2016 | Flag
Comment hidden because of low score. Click to expand.
5
of 11 vote

First, combine all lists into one big list, for each item keeping track of the list it's from and the value of the item. You get a data structure that (conceptually) looks like this:

0         10        15             24  26
  4    9      12              20
     5                      18                   30

Now you start going through this new list item by item until you have the first item from each list (in this case 0,4,5), and you calculate the range (5). Now you move through the list one element at a time. Each time you find an element from a given list, you select that element (so you have three indices, and you always move the one to whose list the current element belongs to that element). So the first step is to replace the 4 by the 9, yielding (0,9,5) with a range of 9. If the range is smaller than the minimum range, remember it, else ignore it, so ignore the (0,9,5) range.
The next couple of ranges: (10, 9, 5), (10,12,5), (15, 12, 5), (15, 12, 18), (15, 20, 18), (18,20,24), (18,20,26), (26, 20, 30).

Since you visit every element in every list once, complexity is O(N) where N is the number of elements in the lists all added up.

- Anonymous April 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

I also thought of that method which looks correct, but the complexity looks O(N log k). When combining I think you have to decide form which list you are going to pick the next element(like k-way merging). So for each of N element it takes O(log k).

- anonyguru April 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

good solution. the issue is with the extra space. for keeping the actual index we need extra space. And if the input lists cannot be altered, then we weed an additional list to merge all 3 lists.

- Vin April 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 4 votes

This algorithm doesn't work. Suppose the 5 were an 8 instead. Then the first valid range you get is (0,4,8), with a size of 8. Then you see the 9, consider (0,9,8), and ignore it because it has size 9. Next you see the 10 and consider (10,4,8), which you accept because it has size 6.

The algorithm has missed the better solution of (8,9,10).

- Anonymous April 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You don't ignore (0,9,8) but just do not update your current best solution (0,4,8). So when you see 10 you'll be considering (10,9,8).

- anonyguru April 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

It is O(k) space and O(N*k) time solution.
N : total no. of elements from all the the lists.

- Anonymous April 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

since list are already ordered, you can in generate the sorted list of all of them fast, and keep an additional array with the original list they belonged to:

In the example

0 1
4 0
5 2
9 1
10 0
12 1
15 0
18 2
20 1
22 2
24 0
26 0
30 2

Once you have that, you just have to find the subsequence in the right column which contains K different symbols (at least length K). If there is more than one sequence of length K, just take the one with the minimum range in the right column

I've implemented the sorting in a customized python iterator

lists=[[4, 10, 15, 24, 26],[0, 9, 12, 20],[5, 18, 22, 30]]
import sys
class MyIterator:
	data=[]
	pointersMin=[]
	def __init__(self,lists):
		self.data=lists
		for i in xrange(len(lists)):
			self.pointersMin+=[0]
	def nextMin(self):
		mlist,mvalue=-1,sys.maxint
		for i in xrange(len(self.data)):
			if(self.pointersMin[i]==len(self.data[i])):
				continue
			if(self.data[i][self.pointersMin[i]]<mvalue):
				mlist=i
				mvalue=self.data[i][self.pointersMin[i]]
		self.pointersMin[mlist]+=1
		if(mlist==-1):
			return None,None
		return mvalue,mlist




print lists
it=MyIterator(lists)
val=[]
lids=[]
m,lid=it.nextMin()
while(m!=None):
	print m,lid
	lids+=[lid]
	val+=[m]
	m,lid=it.nextMin()

seqsize=len(lists)
res=(-sys.maxint,sys.maxint)
while(res[0]==(-sys.maxint)):
	for i in xrange(len(lids)-seqsize+1):
		seq=lids[i:(i+seqsize)]
		mval=val[i:(i+seqsize)]
		if(len(set(seq))==len(lists)):
			if((mval[-1]-mval[0])<(res[1]-res[0])):
				res=(mval[0],mval[-1])
	seqsize+=1
print res

It could be optimized for the case of disjoint intervals defined by the groups, where the sequence would be [0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1] by not enlarging the list when adding 3+ items from the same original list.

- Carlos April 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Keep three pointers to the beginning of each of the lists and advance the pointer on the list that has the next smallest value until you reach the end of one of the lists that has the lowest number out of the three. Store the smallest range along the way. So the iterations become (the current index of the pointer is shown in parentheses)

(4), 10, 15, 24, 26
(0), 9, 12, 20
(5), 18, 22, 30
Range: 5

(4), 10, 15, 24, 26
0, (9), 12, 20
(5), 18, 22, 30
Range: 5

4, (10), 15, 24, 26
0, (9), 12, 20
(5), 18, 22, 30
Range: 5

4, (10), 15, 24, 26
0, 9, (12), 20
(5), 18, 22, 30
Range: 7

4, 10, (15), 24, 26
0, 9, (12), 20
(5), 18, 22, 30
Range: 10

4, 10, (15), 24, 26
0, 9, (12), 20
5, (18), 22, 30
Range: 6

4, 10, (15), 24, 26
0, 9, 12, (20)
5, (18), 22, 30
Range: 5

4, 10, (15), 24, 26
0, 9, 12, (20)
5, 18, (22), 30
Range: 7

4, 10, 15, (24), 26
0, 9, 12, (20)
5, 18, (22), 30
Range: 4

You can stop at this point since the lowest number in the range belongs to the list that has no more elements, which means you can't improve upon this.

- Anonymous April 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Instead of starting it from first element, we can start that same process with the median elements of all arrays. It will optimize the solution further.

BTW, its a simple and great approach!

- Shakti April 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How can we prove the correctness of this algorithm? It is somewhat similar to the one with highest votes, except that it removes the element from the set which has next minimum value, whereas the other answer removes the element which itself is minumum.

So which one is correct? How to prove it?

- Nawaz April 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We do not need to start from the beginning, as suggested here. Instead, start at tails. The smallest of the tails is the lower bound of the range guaranteed. The issue is to find the upper bound. Of course the upper bound cannot be more than the max of all tails.

So start with the max of tails as upper bound. To best this estimation, compare the next smaller number than this tail (in the same list as the max of tails, of course). If this number is greater than lower bound (which is fixed), then continue looking. Stop when your number is smaller than lower bound.

This way, you don't need search all the K lists. Here is the pseudo code:

For each list in K collection:
	Get the tailValue and eval the running minimum (minOfTails)
	Get the tailValue and eval the running maximum (maxOfTails)
:loop end

Set the range lower bound = minOfTails //This is our lower bound

//Now take the Kth list whose tail is maximum
For each item in the Kth list: (reverse loop, from the tail)
         Check: If minOfTails is less than the element
         If yes, continue
         If no, then set the element as upper bound of range and exit
:loop end
Set the last known KList value greater than minOfTails as upper bound of range.

- whitenoise April 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

1 4 7 100 200 300 500
2 5 8 125 225 325 525
3 6 9 150 250 350 550

All of u guys, both who r starting from the begining of the list and those who r starting frm the end of the list jst check ur algo. for the above example and comment the correctness of ur algo...!!!

- Mittal June 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1.Do a k-way merge. Use k pointers to point to the start of each list.
2.Find the min and max elements among these k elements and find the difference as range (min and max are elements of range). If range is less than previous range, update it
3.Move to the next index in the list having the minimum value. Go to step 2

- Rajesh April 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/usr/bin/env python
# lrange.py - Find the smallest range of numbers that would include at
#             least one item from each input list Ki. All lists are
#             sorted.
#             Program reads one list per line with items separated by
#             space.

import sys

# K[i][j] is the jth item of the ith list
K = [[int(x) for x in l.strip().split()] for l in sys.stdin]

# M[i] is an index to K[i]
M = [0] * len(K)

# minI is an index to M for the smallest K[i][M[i]] for all i
minI = min(((i, K[i][M[i]]) for i in xrange(len(K))), key=lambda x: x[1])[0]

# maxI is an index to M for the largest K[i][M[i]] for all i
maxI = max(((i, K[i][M[i]]) for i in xrange(len(K))), key=lambda x: x[1])[0]

Rl = K[minI][M[minI]]
Rh = K[maxI][M[maxI]]

while M[minI] < len(K[minI]) - 1:

  # Try to reduce the range by proceeding to next element in the K list
  # with lowest value M[i] is pointing at.

  M[minI] += 1
  oldMinI = minI

  # To get 'n log k' performance, maintain a heap for minI

  minI = min(((i, K[i][M[i]]) for i in xrange(len(K))), key=lambda x: x[1])[0]

  if K[oldMinI][M[oldMinI]] > K[maxI][M[maxI]]:
    maxI = oldMinI

  # If the new range is smaller than the current one, replace

  if K[maxI][M[maxI]] - K[minI][M[minI]] < Rh - Rl:
    Rl = K[minI][M[minI]]
    Rh = K[maxI][M[maxI]]

print 'Range: %d - %d incl.' % (Rl, Rh)

As it is, this runs in O(n.k) where n is the total number of elements in all lists and k is the number of lists. To make it run in O(n.log k), use a heap to keep M sorted for min value.

- Mansour April 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct ArrayElementIndirectCompare 
{
public:
    ArrayElementIndirectCompare(const vector<vector<int> > &v) : v_(v) {}

    bool operator()(pair<int, int> one, pair<int, int> two)
    {
        return v_[one.first][one.second] > v_[two.first][two.second];
    }

private:
    const vector<vector<int> > &v_;
};

void
SmallestMutualRange(const vector<vector<int> > &v, int &lo, int &hi)
{
    lo = numeric_limits<int>::max();
    hi = numeric_limits<int>::min();

    int K = v.size();

    ArrayElementIndirectCompare comp(v); 
    vector<pair<int, int> > heap; // heap of pairs <array index, element index>
    for (int i = 0; i < K; i++) {
        heap.push_back(pair<int, int>(i, 0));
        if (v[i][0] < lo) {
            lo = v[i][0];
        }
        if (v[i][0] > hi) {
            hi = v[i][0];
        }
    }
    make_heap(heap.begin(), heap.end(), comp);

    int curr_lo = lo;
    int curr_hi = hi;

    while (true) {
        pop_heap(heap.begin(), heap.end(), comp);
        pair<int, int> p = heap.back();
        if ((p.second + 1) >= v[p.first].size()) {
            break;
        }
        int added = v[p.first][p.second + 1];
        if (added > curr_hi) {
            curr_hi = added;
        }
        heap.back() = pair<int, int>(p.first, p.second + 1);
        push_heap(heap.begin(), heap.end(), comp);
        p = heap.front();
        curr_lo = v[p.first][p.second];

        if ((curr_hi - curr_lo) < (hi - lo)) {
            lo = curr_lo;
            hi = curr_hi;
        }
    }
}

- Anonymous April 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The merging and coloring solution is the general correct approach. Here's my implementation in Java, it takes O(n*log(k)) i believe, where n is the total number of elements in all k lists.

//class used within FindMinSubrange.java for encapsulating color and value information
class Node implements Comparable<Node>{
	int color, value;
	public Node(int color, int value){
		this.color = color;
		this.value = value;
	}
	public int compareTo(Node n){
		return this.value - n.value;
	}
}

import java.util.*;
public class FindMinSubrange {
	public static void main(String[] args){
		int[][] lists = {{4, 10, 15,24,26}, {0,9,12,20}, {5,7,11,18,22,30}};
		int[] minRange = findMinSubrange(lists);
		ArrayFactory.printArray(minRange);
	}
	
	public static int[] findMinSubrange(int[][] lists){
		int k = lists.length;
		ArrayList<Node> mergedList = merge(lists);

		//frequencies contains the number of occurrences of a  
		int[] frequencies = new int[k];
		
		//left and right indices of the current range we're looking at
		int leftIndex = 0, rightIndex = 0;
		
		//minimum range found so far
		int[] minRange = {0, mergedList.get(mergedList.size()-1).value};
		
		//number of lists that we have not found a number for in the given range
		//when remainingIndex == 0, then we have found a range with at least one number from each list
		int remainingIndex = k;
	
		//lists of nodes in the current range
		Deque<Node> currentRange = new LinkedList<Node>();
		
		for(;rightIndex < mergedList.size(); rightIndex++){
			Node nextNode = mergedList.get(rightIndex);
			currentRange.offerLast(nextNode);
			if(frequencies[nextNode.color]++ == 0)
				remainingIndex--;
			if(remainingIndex == 0){ //found a new range, check to see if new min
				//trim the front of the range of any extra numbers
				while(frequencies[currentRange.peekFirst().color] > 1){
					frequencies[currentRange.peekFirst().color]--;
					currentRange.pollFirst();
					leftIndex++;
				}
				//check if found a new minimum range
				if(mergedList.get(rightIndex).value - mergedList.get(leftIndex).value < minRange[1] - minRange[0] ){
					minRange[0] = mergedList.get(leftIndex).value;
					minRange[1] = mergedList.get(rightIndex).value;
				}
				leftIndex++;
				remainingIndex++;
				frequencies[currentRange.pollFirst().color]--;
			}
		}
		return minRange;
	}
	
	//merge k sorted lists into one sorted list with identifying color information
	// color is an int in the interval [0, k-1] that represents which list it came from
	private static ArrayList<Node> merge(int[][] lists){ 
		int totalSize = 0, k = lists.length;
		PriorityQueue<Node> nodeHeap = new PriorityQueue<Node>(k);
		//count the total number of elements in the lists while also populating the heap with the minimum from each list
		for(int i=0; i<k; i++){
			totalSize += lists[i].length;
			nodeHeap.offer(new Node(i, lists[i][0]));
		}
		ArrayList<Node> mergedList = new ArrayList<Node>(totalSize);
		
		//this array contains a pointer to the next element to merge in each of the k lists
		//initialize it to 1 since we already added the first element of each list to the heap
		int[] indices = new int[k];
		Arrays.fill(indices, 1);
		
		//extract and insert the head of the heap into the merged list.
		//whichever list the head belonged to, add the next element from that list into the heap
		while(!nodeHeap.isEmpty()){
			Node currentMin = nodeHeap.poll();
			int currentIndex = currentMin.color;
			mergedList.add(currentMin);
			if(indices[currentIndex] < lists[currentIndex].length){
				nodeHeap.offer(new Node(currentIndex, lists[currentIndex][indices[currentIndex]]));
				indices[currentIndex]++;
			}
		}
		return mergedList;
	}
}

- ericaturner0 April 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem can be solved in O(nlogk)

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#include <climits>
using namespace std;

typedef vector<int> vi; 
typedef vector<vi> vvi; 
typedef pair<int, pair<int, int> > ii; 
#define sz(a) int((a).size()) 
#define pb push_back 
#define all(c) (c).begin(),(c).end() 
#define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++) 
#define present(c,x) ((c).find(x) != (c).end()) 
#define cpresent(c,x) (find(all(c),x) != (c).end())

struct range
{
	int beg;
	int end;
	inline bool operator < (const range &rhs) const
	{
		return (end-beg) < (rhs.end-rhs.beg);
	}
	inline bool operator == (const range &rhs) const
	{
		return (end-beg) == (rhs.end-rhs.beg);
	}
};

class mycmp
{
	bool reverse;
	public:
  	mycmp (const bool& revparam=false)
    	{
		reverse=revparam;
	}
	
  	bool operator() (const ii& lhs, const ii& rhs) const
  	{
		if(reverse)
		{
			if(lhs.first != rhs.first) return lhs.first > rhs.first;
			if(lhs.second.first != rhs.second.first) return lhs.second.first > rhs.second.first;
			return lhs.second.second > rhs.second.second;
		}
		
		if(lhs.first != rhs.first) return lhs.first < rhs.first;
		if(lhs.second.first != rhs.second.first) return lhs.second.first < rhs.second.first;
		return lhs.second.second < rhs.second.second;

      	}
};
    
range findMinRange(vvi &list)
{
	range minRange = {INT_MAX, INT_MIN}, currRange = {INT_MAX, INT_MIN};
	priority_queue <ii , vector<ii>, mycmp> heap(mycmp(true));
	ii p, tp;
	vvi:: iterator i;
	for(i = list.begin(); i != list.end(); ++i) 
        {
		if((*i).begin() != (*i).end())
  		{
			heap.push(make_pair((*i)[0], make_pair(i - list.begin(), 0)));
			if(currRange.beg > (*i)[0]) currRange.beg = (*i)[0];
			if(currRange.end < (*i)[0]) currRange.end = (*i)[0];
		}		  
        }
	minRange = (range) {currRange.beg, currRange.end};
	while(!heap.empty())
  	{
		p = heap.top();
		heap.pop();
		if(list[p.second.first].begin()+p.second.second+1 != list[p.second.first].end())
	  	{
	        	heap.push(make_pair(list[p.second.first][p.second.second+1], make_pair(p.second.first, p.second.second+1)));
			tp = heap.top();
			currRange.beg = tp.first;
			if(currRange.end < list[p.second.first][p.second.second+1])
				currRange.end = list[p.second.first][p.second.second+1];
			if(currRange < minRange)
			  	minRange = (range) {currRange.beg, currRange.end}; 
		}
      		else
  			break;		  
	}
	return minRange;	
}


int main()
{
	int a[] = {4, 10, 15, 24, 26}; 
        int b[] = {0, 9, 12, 20}; 
	int c[] = {5, 18, 22, 30}; 
	vi v1(a, a + sizeof(a)/sizeof(int));
        vi v2(b, b + sizeof(b)/sizeof(int));
	vi v3(c, c + sizeof(c)/sizeof(int));
        vvi list;
	list.push_back(v1);
	list.push_back(v2);
	list.push_back(v3);
	range minRange = findMinRange(list);
	cout<<minRange.beg<<" "<<minRange.end<<endl;
	return 0;	
}

- LoL April 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Working solution

#include<iostream>
#include<vector>
#include<climits>

int findMin(int a, int b, int c) {
    if (a < b) {
        if (a < c) return a;
    } else {
        if (b < c) return b;
    }
    return c;
}

int findMax(int a, int b, int c) {
    if (a > b) {
        if (a > c) return a;
    } else {
        if (b > c) return b;
    }
    return c;
}

int main() {
    const int array[] = {4, 10,15,21,26};
    std::vector<int> vA(array, array + (sizeof(array)/sizeof(array[0])));

    const int arrayB[] = {0, 9, 12, 20};
    std::vector<int> vB(arrayB, arrayB + (sizeof(arrayB)/sizeof(arrayB[0])));

    const int arrayC[] = {5, 18, 22, 30};
    std::vector<int> vC(arrayC, arrayC + (sizeof(arrayC)/sizeof(arrayC[0])));

    int ia = 0;
    int ib = 0;
    int ic = 0;
    int min = 0, max = INT_MAX;
    int finalMin = 0, finalMax = INT_MAX;
    int range = INT_MAX;
    while(ia < vA.size() && ib < vB.size() && ic < vC.size() ) {
       min = findMin(vA[ia], vB[ib], vC[ic]);
       max = findMax(vA[ia], vB[ib], vC[ic]);

       if((max - min) < range) {
           range = max - min;
           finalMin = min;
           finalMax = max;
       }

       if(min == vA[ia]) ia++;
       else if (min == vB[ib]) ib++;
       else ic++;
    }

    std::cout << "range is (" << finalMin << " - " << finalMax << ")\n";
    return 0;
}

- Anonymous April 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

size_t findHighBorder( const size_t value, size_t* arr, const size_t length )
    {
        for( size_t i = 0; i < length; i++ )
        {
            if( value < arr[i] )
            {
                return arr[i];
            }
        }
        return value;
    }

void Test16759664()
    {
        size_t L1[] = {4, 10, 15, 24, 26};
        size_t L2[] = {0, 9, 12, 20};
        size_t L3[] = {5, 18, 22, 30};

        map<size_t, size_t>  keyer;

        keyer[ L1[0] ] = L1[ _countof(L1)-1  ];
        keyer[ L2[0] ] = L2[ _countof(L2)-1  ];
        keyer[ L3[0] ] = L3[ _countof(L3)-1  ];

        const size_t lowerBorder = (*keyer.begin()).second;

        std::set<size_t> higher;

        higher.insert( findHighBorder( lowerBorder, L1, _countof(L1) ) );
        higher.insert( findHighBorder( lowerBorder, L2, _countof(L2) ) );
        higher.insert( findHighBorder( lowerBorder, L3, _countof(L3) ) );

        size_t higherBorder = (*higher.rbegin());

        for( std::set<size_t>::iterator iter = higher.begin(); iter != higher.end(); ++iter )
        {
            if( *iter != lowerBorder )
            {
                higherBorder = *iter;
                break;
            }
        }
        std::cout << "range is (" << lowerBorder << " - " << higherBorder << ")\n";
    }

- LBaralgeen April 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package ArrayImpl;

import java.util.Arrays;

public class FindRangeAcrossArrays {

	/**
	 * You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.

		For example,
		List 1: [4, 10, 15, 24, 26]
		List 2: [0, 9, 12, 20]
		List 3: [5, 18, 22, 30]		
		The smallest range here would be [20, 24] as it contains 24 from list 1, 
		20 from list 2, and 22 from list 3.
	 * @param args
	 * Look at the ranges like this
	 *(4,0,5),(4,9,5),(10,9,5),(10,9,18),(10,12,18),(15,12,18),(15,20,18),(15,20,22),(24,20,22);
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int lst1[] = { 4, 10, 15, 24, 26};
		int lst2[] = { 0, 9, 12, 20};
		int lst3[] = { 5, 18, 22, 30};
		
		int result[] = {lst1[0], lst2[0], lst3[0]};
		int positionResult[] = {0,0,0};
		int whichlist = 0;
		int minRangeFound = Integer.MAX_VALUE, rangeValue = 0;
		for (int i = 0, j = 0, k = 0; i < lst1.length  && j < lst2.length  && k <= lst3.length;)
		{	
			rangeValue = findMaximumNumber(result) - findMinimumNumber(result);
			if(rangeValue < minRangeFound)
			{
				positionResult[0] = i;
				positionResult[1] = j;
				positionResult[2] = k;
				minRangeFound = rangeValue;
			}
			whichlist = findMinimumNumberIndex(result);
			//System.out.println(whichlist + " i = " + i + ", j = " + j + ", k = " + k);
			if(whichlist == 0)
				result[0] = ++i < lst1.length? lst1[i]: result[0];
			else if (whichlist == 1)
				result[1] = ++j < lst2.length? lst2[j]: result[1];
			else
				result[2] = ++k < lst3.length? lst3[k]: result[2];
			
			//System.out.println(Arrays.toString(result));
			//System.out.println(Arrays.toString(positionResult));
		}
		result[0] = lst1[positionResult[0]];
		result[1] = lst2[positionResult[1]];
		result[2] = lst3[positionResult[2]];
		System.out.println("Minimum Range Found is [" + findMinimumNumber(result) 
		                   + " , " + findMaximumNumber(result) + "]");
	}
	
	public static int findMinimumNumberIndex(int x[])
	{
		if(x[0] < x[1] && x[0] < x[2])
			return 0;
		else if (x[1] < x[0] && x[1] < x[2])
			return 1;
		else
			return 2;		
	}
	
	public static int findMinimumNumber(int x[])
	{
		if(x[0] < x[1] && x[0] < x[2])
			return x[0];
		else if (x[1] < x[0] && x[1] < x[2])
			return x[1];
		else
			return x[2];		
	}
		
	public static int findMaximumNumber(int x[])
	{
		if(x[0] > x[1] && x[0] > x[2])
			return x[0];
		else if (x[1] > x[0] && x[1] > x[2])
			return x[1];
		else
			return x[2];		
	}

}

- Anonymous April 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python code

import heapq

def kLists(L):
    heap = []
    end = False
    for l in L :
        thisRange = max(l) - min(l)
        heap.append(min(l))
        heapq.heapify(heap)
            
    while not end:
        elem = heapq.heappop(heap)
        print elem
        for l in L :
            
            if elem in l:
                #print l
                
                l.remove(elem)
                #print l
                if len(l) == 0:
                    end = True
                    break
                heapq.heappush(heap,l[0])
    print heap
    

def minL(l):
    m =  min(float(s) for s in l)
    return m

def maxL(l):
    m =  max(float(s) for s in l)
    return m

if __name__ == "__main__":
    L = [
        [4, 10, 15, 24, 26],
        [0, 9, 12, 20],
        [5, 18, 22, 30],
        ]
    kLists(L)

output : [20, 24]

- EK MACHCHAR May 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution written in C#

public class Range
    {
        public int Min { get; set; }
        public int Max { get; set; }
        public int Cost { get { return this.Max - this.Min; } }

        public Range(int min, int max)
        {
            this.Min = min;
            this.Max = max;
        }

        public int CompareTo(Range range)
        {
            return this.Cost.CompareTo(range.Cost);
        }

        public override string ToString()
        {
            return String.Format("[{0}, {1}]", this.Min, this.Max);
        }
    }

    public class Ranger
    {
        private List<List<int>> lists;
        private int[] indices;

        public Ranger(List<List<int>> lists)
        {
            this.lists = lists;

            // create an array to keep track of the indices during iterations
            // initially all are 0's.
            indices = new int[lists.Count]; 
        }

        private int IndexOfNextMin()
        {
            int index = -1;
            int min = Int32.MaxValue;
            for (int x = 0; x < lists.Count; x++)
            {
                if (indices[x] < lists[x].Count - 1)
                {
                    int val = lists[x][indices[x] + 1];
                    if (val < min)
                    {
                        min = val;
                        index = x;
                    }
                }
            }

            return index;
        }

        private Range CalculateCurrentRange()
        {
            int min = Int32.MaxValue;
            int max = Int32.MinValue;
            for (int x = 0; x < lists.Count; x++)
            {
                int val = lists[x][indices[x]];
                if (val < min)
                {
                    min = val;
                }

                if (val > max)
                {
                    max = val;
                }
            }

            return new Range(min, max);
        }

        public Range GetMinimumRange()
        {
            // initial range
            Range range = this.CalculateCurrentRange();

            // walk through to find a better range
            while (true)
            {
                // iterate
                int index = IndexOfNextMin();
                if (index >= 0)
                {
                    indices[index]++;

                    Range temp = CalculateCurrentRange();
                    if (range.CompareTo(temp) > 0)
                    {
                        // we have a better range
                        range = temp;
                    }
                }
                else
                {
                    break;
                }
            }

            return range;
        }
    }


        public static void Main(string[] args)
        {
            // data
            List<List<int>> lists = new List<List<int>>()
            {
                new List<int>(){4, 10, 15, 24, 26},
                new List<int>(){0, 9, 12, 20},
                new List<int>(){5, 18, 22, 30},
            };

            Ranger ranger = new Ranger(lists);
            Range range = ranger.GetMinimumRange();
            Console.WriteLine(range);
        }

- impala May 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MinRangeFinder
    {
        /*
         * {1,4,7,9,10,34,48}
         * {23,24,25,26,27,28,29,33,111,222}
         * {7,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33}
         * solution: {34,33,33}
        */
        public static int[] FindMinRange(int[] a, int[] b, int[] c)
        {
            // keep track of the min range
            int[] minRange = new int[3] { a[0], b[0], c[0] };
            int minRangeValue = GetRange(a[0], b[0], c[0]);

            // arrays
            int[][] arrays = new int[][] { a, b, c };
            int[] indices = new int[] { 0, 0, 0 };

            while (TryAdvanceToNextMin(arrays, indices))
            {
                int rangeValue = GetRange(a[indices[0]], b[indices[1]], c[indices[2]]);
                if (rangeValue < minRangeValue)
                {
                    minRange = new int[] { a[indices[0]], b[indices[1]], c[indices[2]] };
                    minRangeValue = rangeValue;
                }
            }

            return minRange;
        }

        private static int GetRange(int x, int y, int z)
        {
            return Math.Max(Math.Max(x, y), z) - Math.Min(Math.Min(x, y), z);
        }

        private static bool TryAdvanceToNextMin(int[][] arrays, int[] indices)
        {
            int arrayIndexToAdvance = -1;
            int minVal = int.MaxValue;
            for (int i = 0; i < arrays.Length; i++)
            {
                if (arrays[i].Length > indices[i] + 1)
                {
                    if (arrays[i][indices[i] + 1] < minVal)
                    {
                        arrayIndexToAdvance = i;
                        minVal = arrays[i][indices[i] + 1];
                    }
                }
            }

            if (arrayIndexToAdvance > -1)
            {
                indices[arrayIndexToAdvance]++;
                return true;
            }

            return false;
        }
    }

- alexb7 June 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My idea is that the range's lower bound is the minimum of the largest element in the k lists, so it is range_lower_bound = min( 26, 20, 30 ) in the example. Then we try to find a set(call it smallest_larger_than_lower_bound_set, ={ 24, 22 } in the example ) of elements, who is the smallest element that is larger than the range_lower_bound in every array, if we find that the array contains range_lower_bound, we emit the array because it means the range will contain at least one element of the array(the range_lower_bound, actually), then range_upper_bound = max( smallest_larger_than_lower_bound_set ).
The proof is simple, if lower bound v > range_lower_bound, then array that contains the range_lower_bound as largest element will not have a element in the range, so range_lower_bound is the optimal lower bound;
if the upper bound v < range_upper_bound, and obviously v >= range_lower_bound, and the array contains the range_upper_bound will not have a element in the range, because the there're only two kinds of element in the array: elements < range_lower_bound and elements >= range_upper_bound > v, so no elements in the array will occurs in the range.
And here is my code in C++, the time complexity is O(kn), where k is the number of lists, and n is the number of elements in the list:

#include <iostream>
#include <vector>

void min_range( const std::vector< std::vector<int> >& vec )
{
	int k = vec.size();
	std::vector< int > ranges( k, 0 );
	int min = vec[0].back();
	for( int i = 0; i < k; ++i ) min = std::min( min, vec[i].back() );

	for( int i = 0; i < k; ++i )
	{
		for( std::size_t j = 0; j < vec[i].size(); ++j )
		{
			if( vec[i][j] == min ) 
			{
				ranges[i] = -1;
				break;
			}
			else if( vec[i][j] > min )
			{
				ranges[i] = j;
				break;
			}
		}
	}

	int max = min;
	for( int i = 0; i < k; ++i )
	{
		if( ranges[i] == -1 ) continue;
		max = std::max( max, vec[i][ranges[i]] );
	}

	std::cout << "[" << min << "," << max << "]" << std::endl;
}

int main( int argc, char* argv[] )
{
	int a0[] = { 4, 10, 15, 24, 26 };
	int a1[] = { 0, 9, 12, 20 };
	int a2[] = { 5, 18, 22, 30 };

	std::vector< std::vector<int> > vec;
	std::vector<int> tmp0( a0, a0 + 5 );
	vec.push_back(tmp0);
	std::vector<int> tmp1( a1, a1 + 4 );
	vec.push_back(tmp1);
	std::vector<int> tmp2( a2, a2 + 4 );
	vec.push_back(tmp2);

	min_range(vec);

	return 0;
}

- weijjcg August 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def smallest(lists):
    minRange=float("inf")
    minListIndex=0
    maxList=0
    minimum=float("inf")
    maximum=0
    index=0
    localMinRange=0
    inRange=[]
    for i in range(0,len(lists)):
        inRange.append(lists[i][0])
        if(lists[i][0]<minimum):
            minimum=lists[i][0]
            minListIndex=i
        if(lists[i][0]>maximum):
            maximum=lists[i][0]

    minRange=maximum-minimum
    minList=[]
    
    index=lists[minListIndex].index(minimum)
    while True:
        index=lists[minListIndex].index(minimum)
        if index+1>len(lists[minListIndex])-1:
            break
        else:
            inRange.insert(minListIndex,lists[minListIndex][index+1])
            inRange.remove(lists[minListIndex][index])
            
            minListIndex=inRange.index(min(inRange))
            
            minimum=min(inRange)
            localMinRange=(max(inRange)-min(inRange))
            if localMinRange<minRange:
                minRange=localMinRange
                minList=inRange
            
            #print inRange
            
    output=[min(minList),max(minList)]
    return output

- eric61213 October 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class KListsSmallestRange {
    public static void main(String[] args)
    {
        int[][] arr = new int[][]{{4, 10, 15, 24, 26},{0, 9, 12, 20},{5,13, 18, 22, 30}};
        
        findRange(arr);
    }
    
    public static void findRange(int[][] arr)
    {
        
        Queue<Integer> min = new PriorityQueue(arr.length);
        Map<Integer,Integer> rows = new HashMap();
        Map<Integer,Integer> cols = new HashMap();
        Map<Integer,Integer> maxCols = new HashMap();
        List<List> allCom = new ArrayList();
        int minRange = 0;
        int minRangeIndex = 0;
        boolean looping = true;
        int minVal = Integer.MAX_VALUE;
        int maxVal = Integer.MIN_VALUE;
        List cCom = new ArrayList();
        
        for(int i=0;i<arr.length;i++)
        {
            
            int value = arr[i][0];

            if(value<minVal)
                minVal = value;
            if(value>maxVal)
                maxVal = value;

            min.add(value);
            rows.put(value, i);
            cols.put(value, 0);
            cCom.add(value);
            maxCols.put(i, arr[i].length);
        }
        
        minRange = maxVal - minVal;
        minRangeIndex = 0;
        allCom.add(cCom);
        
        while(looping)
        {
            minVal = Integer.MAX_VALUE;
            maxVal = Integer.MIN_VALUE;
            
            List ncList = allCom.get(allCom.size()-1);
            
            int cMin = min.poll();
            int cRow = rows.get(cMin);
            int cCol = cols.get(cMin);
            if(cCol == maxCols.get(cRow)-1)
                looping = false;
            else
            {
                List nList = new ArrayList();
                for(int k=0;k<ncList.size();k++)
                {
                    int lVal = (Integer)ncList.get(k);
                    if(cMin != lVal)
                    {
                        nList.add(lVal);
                    }
                }
                
                int cValue = arr[cRow][cCol+1];
                nList.add(cValue);
                min.add(cValue);
                rows.put(cValue, cRow);
                cols.put(cValue, cCol+1);
                
                for(int k=0;k<nList.size();k++)
                {
                    int lVal = (Integer)nList.get(k);
                    
                    if(lVal<minVal)
                        minVal = lVal;
                    if(lVal>maxVal)
                        maxVal = lVal;
                }
                int newRange = maxVal - minVal;
                if(newRange < minRange)
                {
                    minRange = newRange;
                    minRangeIndex  = allCom.size();
                }
                allCom.add(nList);
            }
        }
        
        System.out.println("Min Range:"+minRange);
        System.out.println("Min range set:"+allCom.get(minRangeIndex));
        
    }
}

- Waseem October 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Im not sure this is bugfree....
L(i) is the shorted list, then for each element in L(i), find the nearest element in other list, memory this range, then loop for other element in L(i). then according to the memory, find the shortest range

- cestbon November 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution:
1) Find the list with the least number of elements. Let's call that list K.
2) Loop through all elements of list K
3) For each element of K[i], find the closest range that can include K[i], using numbers from other lists.
4) Compare all the ranges we found in step 3: best range for K[0], best range for K[1],... . Pick the best range out of them all.

Example
List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]

1) List 2 and List 3 both have same number of elems. We can pick List as the seed List.
2) Loop through all elements of List 2
3)
For '0': best range that can represent '0' is [0,5]
For '9': best range that can represent '9' is [5,10]
For '12': best range that can represent '12' is [12,18]
For '20': best range that can represent '20' is [20,24]

Out of those 4 ranges, [20,24] is the best

- hugh.hn November 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

JavaScript Solution:

function find(lists) {
    "use strict";

    // Sort lists
    lists = lists.map(function (list) {
        return list.sort(function(a,b) {return a-b;});
    });

    // Find all possible ranges
    var ranges = [];
    lists.forEach(function (list, i) {
        list.forEach(function (n) {
            if(i+1 !== lists.length){
                lists[i+1].forEach(function (m) {
                    if(n>m)
                        ranges.push([m,n]);
                    else
                        ranges.push([n,m]);
                });
            }
        });
    });

    // filter out ranges that do not include one item from each list
    ranges = ranges.filter(function checkRange (range) {
        var n = range[0];
        var m = range[1];

        // Make a hash that is reperesnting lists.
        var includesHash = lists.map(function () {
            return false;
        });

        // for each integer from beginning of range to end of it
        intloop: for(var i = n; i <= m; i++){

            // for each list
            listloop: for(var j = 0; j < lists.length; j++){
                var list = lists[j];

                // for each item of the list
                itemloop: for(var k = 0; k< list.length; k++){
                    var item = list[k];

                    // if item equal to the integer we are checking against (i)
                    if(item === i){

                        // this list includes this number. break list loop
                        includesHash[j] = true;
                        break listloop;
                    }
                }
            }
        }

        // if all lists pass the test return true.
        return includesHash.filter(function (includes) {
            return includes === true;
        }).length === lists.length;
    });

    // sort ranges by width of each range
    ranges = ranges.sort(function (range1, range2) {
        return (range1[1] - range1[0]) - (range2[1] - range2[0]);
    });

    // return smallest range
    return ranges[0];
}



console.log(find([
    [4, 10, 15, 24, 26],
    [0, 9, 12, 20],
    [5, 18, 22, 30]
]));

- Mocoder December 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For each integer in any list between the biggest small number and the largest number find the nearest number in each list and compute the range. You might of course find multiple solutions.

- Andrew January 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another js solution, does bruteforce, not optimal but works.

var a = [4, 10, 15, 24, 26] 
var b = [0, 9, 12, 20] 
var c = [5, 18, 22, 30]

var res = findRange(a, b, c);

console.log(res);


var a = [1,2,3] 
var b = [4,5,6] 
var c = [9,10]

var res = findRange(a, b, c);

console.log(res);

var a = [11,22,33] 
var b = [10,24,256] 
var c = [12,13]

var res = findRange(a, b, c);

console.log(res);

function findRange (a, b, c){

  [a,b,c].forEach(function(list){
    if(list.length == 0) throw 'list cannot be empty';
  });

  var range = {
    start: null,
    length: null
  };

  var  mergedList = mergeLists(a, b, c);
  mergedList.forEach(function(item) {
    var rangeLength = calculateRangeLength(item, a,b,c);
    if( rangeLength && (!range.length || rangeLength < range.length))
      range = {
        start: item,
        length: rangeLength
      }
  });

  return range;
}

function mergeLists (a, b, c){
  var base = a.map(function(x){ return x;});
  base = mergeInto(base, b);
  base = mergeInto(base, c);
  return base;
}

/*
base: [4, 10, 15, 24, 26] 
other: [0, 9, 12, 28] 

base: [4, 10] 
other: [11] 

base: [4, 10] 
other: [6] 

base: [4, 10] 
other: [0] 
*/
function mergeInto (base, other){
  
  for(var i=0; i<other.length; i++){
    var curItem = other[i];
    var inserted = false;

    for(var baseIterator = base.length - 1; baseIterator > -1; baseIterator--){
      var baseItem = base[baseIterator];
      if (curItem < baseItem) {
         base[baseIterator + 1] = baseItem; 
      } else  {
        base[baseIterator + 1] = curItem; 
        inserted = true
        break;
      }
    }
    if(!inserted) base[0] = curItem; 
  }
  return base;
}

/*
item: 4
a: [4, 10, 15, 24, 26] 
b: [0, 9, 12, 20] 
c: [5, 18, 22, 30]
*/
function calculateRangeLength(item,a,b,c){
  var minElm = item;
  var maxElm = item;
  var found = false;
  var rangeExists = true;

  [a,b,c].forEach(function(list){
  	found = false;
    list.forEach(function(curItem){
      if(found || curItem < minElm) return;
      found = true;
      if(maxElm < curItem) maxElm = curItem;
    });
    if (!found) rangeExists = false;
  });
    
  if (!rangeExists) return null;;
  return maxElm - minElm;
}

- grandbora January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution:
1. Create an Item object for every value containing a min value, max value, and referenced lists
2. For every Item object, compare every list.
- If the list is already referenced, return
- If the value within the range of min & max, add this list as reference and return
- If the value is greater than a temporary max for this item, update temporary max and continue
- Update maxValue for item and reference this list, continue
3. For every item, call GetRange() and compare with temporary range, if its smaller, make it new temp

Here's my code in c#:

using System;
using System.Collections.Generic;

namespace ListProblem
{
	
	class MainClass
	{
		public static int globalNum = 0;
		public static List<List<int>> allLists = new List<List<int>>();

		public static void Main (string[] args)
		{
			//Instantiate all the lists that I will use as an example
			List<int> list1 = new List<int>(new int[]{4, 10, 15, 24, 26});
			List<int> list2 = new List<int>(new int[]{0, 9, 12, 20});
			List<int> list3 = new List<int>(new int[]{5, 18, 22, 30});

			allLists = new List<List<int>>();
			allLists.Add(list1);
			allLists.Add(list2);
			allLists.Add(list3);

			//Track all the lists that will be used to test ranges 
			List<Item> allItems = new List<Item>();

			//Fill these up, assigning every single one to have both the min and max be an element as the starting one, the moment its been assigned, break the list 
			foreach(List<int> list in allLists) {
				foreach(int num in list) {
					allItems.Add(new Item(num, num, list));
				}
			}

			//Now run the algorithm to adjust is max value, every time adding it to the list
			foreach(Item item in allItems) {
				foreach(List<int> list in allLists) {
					item.CompareWithList(list);
				}
			}

			//Now determine which item actually has the smallest range
			Item tempMin;
			for(int i = 0; i < allItems.Count; i++) {
				if (!allItems[i].HasAllLists()) 	continue;
				if (i == 0) tempMin = allItems[i];
				else {
					if (allItems[i].GetRange() < tempMin.GetRange()) {
						tempMin = allItems[i];
					}
				}
			}
			Console.WriteLine("--------COMPLETED APPLICATION---------");
			tempMin.PrintInfo();
		}

		public class Item {
			public int itemNum;
			public int minVal;
			public int maxVal;
			List<List<int>> usedLists;
			
			public Item(int min, int max, List<int> list ) {
				itemNum 	= ++globalNum;
				minVal 		= min;
				maxVal 		= max;
				usedLists 	= new List<List<int>>();
				usedLists.Add(list);
			}

			public int GetRange() {
				return (maxVal - minVal);
			}

			public void PrintInfo() {
				Console.WriteLine("---------Print info----------");
				Console.WriteLine("Item " + itemNum);
				Console.WriteLine("Min: " + minVal);
				Console.WriteLine("Max: " + maxVal);
			}

			public bool HasAllLists() {
				return usedLists.Count == allLists.Count;
			}

			public void CompareWithList(List<int> list) {
				//Run through a passed list, comparing the values range to the previous values range
				int tempMax = maxVal;
				foreach(int num in list) {

					if (usedLists.Contains(list)) 	return;							//Already found one in this list, don't bother checking 
					if (num < minVal) 				continue;						//Smaller than min, don't bother 
					if (num <= maxVal && num >= minVal) {							//Within range, add it to the list 
						usedLists.Add(list);
						continue;
					}
				
					if (num >= minVal && num <= tempMax) 	tempMax = num;			//If its smaller than a previous one
					if (num > tempMax && tempMax == maxVal) tempMax = num;
				
				}
				if (tempMax > maxVal) {												//Update the max value to the new one 
					maxVal = tempMax;
					usedLists.Add(list);
				}
			}
		}
	}
}

- AddisonRodomista February 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution in C++, based on aasshishh idea. I use C++ STL priority_queue to maintain the smallest element.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct Element {
    int value;
    int idx;
};
inline bool operator<(const Element &a, const Element &b) {
    return (a.value > b.value);
}

void printMinRange(vector< vector<int> > const& L) {
    // We assume L does not contain empty list
    priority_queue<Element> curlist;
    int curpos[L.size()];
    int a = -1, b = -1, c, d, i;

    for (i = 0; i < L.size(); ++i) {
        curpos[i] = 0;
        if (a == -1 || L[i][0] < a)
            a = L[i][0];
        if (b == -1 || L[i][0] > b)
            b = L[i][0];
        curlist.push((Element){L[i][0], i});
    }
    c = a;
    d = b;
    Element e;
    while (true) {
        e = curlist.top();
        curlist.pop();
        if (curpos[e.idx] == L[e.idx].size() - 1)
            break;
        curlist.push((Element){L[e.idx][++curpos[e.idx]], e.idx});
        c = curlist.top().value;
        if (L[e.idx][curpos[e.idx]] > d)
            d = L[e.idx][curpos[e.idx]];
        if (d - c < b - a) {
            a = c;
            b = d;
        }
    }
    cout << a << ',' << b << endl;
}

- Thomas February 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

assume 3 lists of elements
list1:(4,10,16,24,32}
list2:{7,8,12,23,51}
list3:{20,22,25,41,43}

-choose the max element of each list
-max_element={32,51,43}
-take the smallest value of max_element and use it as starting range, START=32.
-so, eliminate list1 since we have one value from the list as a starting range.
-Next, scan through list 1 and list 3 to find the smallest value which is bigger than START.
-Example, list 2 is 51, list 3 is 41. so smalVal={51,41}
-get the largest Value from smalVal as ending range, END=51

so, the answer will be 32-51.

- LueLue June 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

"-Next, scan through list 1 and list 3 to find the smallest value which is bigger than START."

sorry, its suppose to scan list 2 and list3, not list1.

- lueikhong June 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

assume 3 lists of elements
list1:(4,10,16,24,32}
list2:{7,8,12,23,51}
list3:{20,22,25,41,43}

-choose the max element of each list
-max_element={32,51,43}
-take the smallest value of max_element and use it as starting range, START=32.
-so, eliminate list1 since we have one value from the list as a starting range.
-Next, scan through list 2 and list 3 to find the smallest value which is bigger than START.
-Example, list 2 is 51, list 3 is 41. so smalVal={51,41}
-get the largest Value from smalVal as ending range, END=51

- LueLue June 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static class Distance {
        int p1, p2, p3;

        public Distance(int p1, int p2, int p3) {
            super();
            this.p1 = p1;
            this.p2 = p2;
            this.p3 = p3;
        }

        private int getValue() {
            return Math.abs(this.getMaxPoint() - this.getMinPoint());
        }

        public int getMinPoint() {
            return Math.min(this.p1, Math.min(this.p2, this.p3));
        }

        public int getMaxPoint() {
            return Math.max(this.p1, Math.max(this.p2, this.p3));
        }
    }

    // binary search arr for the closest elements to the val
    public static int[] getNearestPoints(int[] arr, int val) {
        assert(arr != null && arr.length > 0);
        if (arr[0] >= val) {
            return new int[] { arr[0] };
        }
        int size = arr.length - 1;
        if (arr[size] <= val) {
            return new int[] { arr[size] };
        }
        int lo = 0;
        int hi = size;
        while (lo <= hi) {
            int mid = (hi + lo) / 2;
            if (arr[mid] == val) {
                return new int[] { val };
            }
            if (arr[mid] < val) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        return new int[] { arr[lo], arr[hi] };
    }

    public static void main(String[] args) {
        int[] arr1 = new int[] { 4 , 10, 15, 24, 26 };
        int[] arr2 = new int[] { 0, 9, 12, 20 };
        int[] arr3 = new int[] { 5 , 18, 22, 30 };

        // consider only points that are close to the arr1[i]
        List<Distance> list = new ArrayList<>();
        for (int i = 0; i < arr1.length; i++) {
            for (int point2 : getNearestPoints(arr2, arr1[i])) {
                for (int point3 : getNearestPoints(arr3, arr1[i])) {
                    list.add(new Distance(arr1[i], point2, point3));
                }
            }
        }

        // find min distance by using Comparator
        Distance p = Collections.min(list, (p1, p2) -> p1.getValue() - p2.getValue());
        System.out.println(p.getMinPoint() + " " + p.getMaxPoint());
    }

- yuri.anischenko June 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists. 

For example, 
List 1: [4, 10, 15, 24, 26] 
List 2: [0, 9, 12, 20] 
List 3: [5, 18, 22, 30] 

The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3.
*/

import java.util.*;
import java.util.stream.*;

class Range implements Comparable<Range> {
    Integer lval = null, rval = null;
    Range() {}
    Range(Integer lval, Integer rval) {
        this.lval = lval;
        this.rval = rval;
    }
    public String toString() {
        return "[" + lval + ".." + rval + "]";
    }
    public int compareTo(Range other) {
        int span = span(), otherSpan = other.span();
        return span < otherSpan ? -1 : span > otherSpan ? 1 : 0;
    }
    public int span() {
        return lval == null || rval == null ? Integer.MAX_VALUE : rval - lval;
    }
    void replaceMaybe(Range range) {
        if (range != null && this.compareTo(range) > 0) {
            lval = range.lval;
            rval = range.rval;
        }
    }
}
class RangeFinder {
    List<List<Integer>> lists;
    // Maintain a "view" on each of the input lists, which can be used to
    // narrow the region of interest as recursion progresses.
    List<List<Integer>> subLists = new ArrayList<List<Integer>>();
    RangeFinder(List<List<Integer>> ll) {
        this.lists = ll;
        // Initialize the sub-lists to the full lists.
        // Note: Recursive calls will successively narrow.
        for (List<Integer> li : lists) subLists.add(li);
    }
    Range find() {
        // Recurse on all numbers in first list to find best range.
        // Note: Recursion base case updates bestRange if the range it's
        // produced is better.
        Range bestRange = new Range();
        for (int n : subLists.get(0)) {
            recurse(1, new Range(n, n), bestRange);
        }
        return bestRange;
    }
    // This is the heart of the algorithm.
    void recurse(int listIdx, Range range, Range bestRange) {
        List<Integer> subList = subLists.get(listIdx);
        int nPrev = 0, numVals = subList.size(), numLists = subLists.size();
        // Loop over (remaining) numbers in current (sub-)list.
        Range ltRange = null, rtRange = null;
        int idx = 0;
        for (int n : subList) {
            if (n >= range.lval) {
                if (idx > 0) {
                    // nPrev must have been < current range's left edge.
                    ltRange = new Range(nPrev, range.rval);
                }
                // Current number may or may not widen rightward.
                rtRange = new Range(range.lval, Integer.max(n, range.rval));
                break;
            } else if (idx == numVals - 1) {
                // This list has only left-widening potential.
                ltRange = new Range(n, range.rval);
                break; // Prevent idx increment
            }
            nPrev = n;
            idx++;
        }
        // Discard nPrev (if applicable) and earlier numbers.
        // Assumption: Can't get out of preceding loop without idx pointing to
        // the index of the first number with potential significance for
        // subsequent roots.
        // Rationale: No subsequent root could provide better solution
        // with nPrev (or earlier) than can current root.
        subLists.set(listIdx, subList.subList(idx, subList.size()));
        if (listIdx + 1 < numLists) {
            if (ltRange != null) recurse(listIdx + 1, ltRange, bestRange);
            if (rtRange != null) recurse(listIdx + 1, rtRange, bestRange);
        } else {
            // Recursion complete. Is either lt or rt range better than
            // current best?
            if (ltRange != null) bestRange.replaceMaybe(ltRange);
            if (rtRange != null) bestRange.replaceMaybe(rtRange);
        }
    }
}

public class SmallestRangeForKLists {
    // Usage:
    // java SmallestRangeForKLists "4  10  15  24  26 | 0  9  12  20 | 5  18  22  30"
    // --OR--
    // java SmallestRangeForKLists <num-lists> <nums-per-list> <min> <max>
    public static void main(String[] args) {
        SmallestRangeForKLists ob = new SmallestRangeForKLists();
        List<List<Integer>> lists = null;
        try {
            switch (args.length) {
                case 0:
                    throw new IllegalArgumentException("Arguments required");
                case 1:
                    lists = ob.createLists(args[0]);
                    break;
                case 4:
                    lists = ob.createLists(Integer.parseInt(args[0]), Integer.parseInt(args[1]), Integer.parseInt(args[2]), Integer.parseInt(args[3]));
                    break;
                default:
                    throw new IllegalArgumentException("Invalid # of arguments.");
            }
        } catch (Exception e) {
            ob.usage(e);
        }
        // Create a RangeFinder and use it find the best range.
        Range range = new RangeFinder(lists).find();

        // Display results...
        System.out.println();
        System.out.println("--Lists--");
        for (List<Integer> li : lists)
            System.out.println(li);
        System.out.println();
        System.out.println("Smallest range: " + range);
    }
    // This overload splits the arg string into lists at `|' chars, with
    // individual numbers separated only by spaces.
    List<List<Integer>> createLists(String s) {
        List<List<Integer>> ll = new ArrayList<List<Integer>>();
        String[] lists = s.trim().split("\\|");
        for (int i = 0; i < lists.length; i++) {
            List<Integer> li = new ArrayList<Integer>();
            String[] nums = lists[i].trim().split("\\s+");
            for (int j = 0; j < nums.length; j++)
                // Conversion may throw NumberFormatException
                li.add(Integer.parseInt(nums[j]));
            // Sort the list in case user didn't...
            Collections.sort(li);
            ll.add(li);
        }
        return ll;
    }
    // This overload creates randomized lists subject to parameters supplied
    // by user.
    List<List<Integer>> createLists(Integer numLists, Integer numsPerList, Integer min, Integer max) {
        List<List<Integer>> ll = new ArrayList<List<Integer>>();
        Random rand = new Random();
        for (int i = 0; i < numLists; i++) {
            List<Integer> li = rand.ints(numsPerList, min, max + 1).sorted().boxed().collect(Collectors.toList());
            ll.add(li);
        }
        return ll;
    }
    void usage(Exception e) {
        if (e != null) {
            System.err.println();
            System.err.println(e);
            System.err.println();
        }
        System.err.println("--Usage--");
        System.err.println("Specify the lists of integers in 1 of the following 2 forms:");
        System.err.println("java SmallestRangeForKLists \"<space-separated-int-list> [ | <space-separated-int-list> [ | ... ] ]\"");
        System.err.println("java SmallestRangeForKLists <num-lists> <nums-per-list> <min> <max>");
        System.err.println();
        System.err.println("--Examples--");
        System.err.println("// Specify lists explicitly.");
        System.err.println("java SmallestRangeForKLists \"4  10  15  24  26 | 0  9  12  20 | 5  18  22  30\"");
        System.err.println("// 7 lists, each containing 10 random ints between 0 and 100 inclusive.");
        System.err.println("java SmallestRangeForKLists 7 10 0 100");
        if (e != null)
            System.exit(1);
    }
}
// vim:ts=4:sw=4:et:tw=78

- Brett Pershing Stahlman July 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public Triple<Integer, Integer, Integer> getMinRange(List<Integer> l1, List<Integer> l2, List<Integer> l3){
	Tripe<Integer, Integer, Integer> mT = Create.newTriple();
	int min = Integer.MAXIMUM;
	for(int e1 : l1){
		for(int e2 : l2){
			if(mod(e1, e2) > min){
				if(e2 >= e1){
					break;
				}
				continue;
			}
			for(e3 : l3){
				int min12 = Math.min(e1, e2);
				if(mod(e3, min12) > min){
					if(e3 > min12){
						break;
					}		
					continue;
				}
				mT = new Triple(e1, e2, e3);
				min = mod(min12, e3);
			}
		}
	}
	return mT;
}

// Worst case complexity O(mno)
// But average case is much less

- tomahawk November 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/usr/bin/python
#    Find the smallest range that includes at least one number from each given
#    list
def smallestRange(inp):
     xmin = []
     for x in inp:
          xmin.append(max(x))
     lowB = min(xmin)
     xmax = []
     for x in inp:
          xmax.append([y for y in x if y >= lowB][0])
     print xmax
     upB = max(xmax)
     return (lowB, upB)

inp = [ [4,10,15,24,26],
        [0,9,12,20],
        [5,18,22,30]]

print smallestRange(inp)

- Frank Wang November 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Brilliant idea by aasshishh. I wrote this python function which would give the results for minrange:
This can be extended to n lists. 'lists' below is a list of lists. So if you have list 1, list2, list3, lists=[list1, list2, list3]

def getMinRange(lists):
	import itertools
	temp={}
	for item in list(itertools.product(*biglist)):
		minval=max(item)-min(item)
		temp[minval]=item
	minrange=(min(temp[min(temp.keys())]),max(temp[min(temp.keys())]))
	return minrange

- Murali December 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A correction: There was a typo in my previous post. The code should be:

def getMinRange(lists):
	import itertools
	temp={}
	for item in list(itertools.product(*lists)):
		minval=max(item)-min(item)
		temp[minval]=item
	minrange=(min(temp[min(temp.keys())]),max(temp[min(temp.keys())]))
	return minrange

- Murali: December 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why [max of minimums, min of maximums] is not an answer?

- mag December 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Collection<List<Integer>> inputData = new LinkedList<>();
        inputData.add(new LinkedList<>(Arrays.asList(4, 10, 15, 24, 26)));
        inputData.add(new LinkedList<>(Arrays.asList(0, 9, 12, 20)));
        inputData.add(new LinkedList<>(Arrays.asList(5, 18, 22, 30)));

        List<Integer> result = solve(inputData);
        StringJoiner stringJoiner = new StringJoiner(", ");

        for (Integer value : result) {
            stringJoiner.add(value.toString());
        }

        System.out.println("Result " + stringJoiner.toString());
    }

    public static List<Integer> solve(Collection<List<Integer>> input) {
        final List<Integer> smallestRange = new LinkedList<>();
        int smallestRangeScore = 0;

        // Conceptually value the list by the first element. By enforcing this ordering on our data structure, the first
        // element value will represent the lower bound and the last will represent the upper bound.
        final SortedSet<List<Integer>> sortedLists = new TreeSet<>(new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return o1.get(0) - o2.get(0);
            }
        });

        // Initialize algorithm state variables.
        sortedLists.addAll(input);
        List<Integer> lowerBoundList = sortedLists.first();
        List<Integer> upperBoundList = sortedLists.last();

        // Initialize the current result.
        smallestRange.add(lowerBoundList.get(0));
        smallestRange.add(upperBoundList.get(0));
        smallestRangeScore = upperBoundList.get(0) - lowerBoundList.get(0);

        while (lowerBoundList.size() > 1) {
            // Remove the list containing the lower bound, remove the lower bound, then re-add (for sorting)
            sortedLists.remove(lowerBoundList);
            lowerBoundList.remove(0);
            sortedLists.add(lowerBoundList);

            // Update algorithm state variables.
            lowerBoundList = sortedLists.first();
            upperBoundList = sortedLists.last();

            // If score is better, save the range, and update the best score.
            int currentRangeScore = upperBoundList.get(0) - lowerBoundList.get(0);
            if (currentRangeScore < smallestRangeScore) {
                // Update the best score.
                smallestRangeScore = currentRangeScore;

                smallestRange.clear();
                smallestRange.add(lowerBoundList.get(0));
                smallestRange.add(upperBoundList.get(0));
            }
        }

        return smallestRange;
    }
}

- james.swan January 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static Map<Integer, Integer> findRange(ArrayList<ArrayList<Integer>> listOfList){
		ArrayList<Integer> list = listOfList.get(0);
		int min = list.get(list.size()-1); 
		int max = 0;
		
		for(int i=1; i<listOfList.size(); i++){
			list = listOfList.get(i); 
			if(list.get(list.size()-1)<min){
				min = list.get(list.size()-1); 
			}
		}
		for(int i=0; i<listOfList.size(); i++){
			list = listOfList.get(i); 
			int listMax = 0, j = list.size()-1; 
			while(j>=0 && list.get(j) > min){
				listMax = list.get(j); 
				j--;
			}
			if (listMax > max && listMax != min) max = listMax; 
		}
		Map<Integer, Integer> range = new HashMap<Integer, Integer>(); 
		range.put(min, max); 
		
		return range; 
	}

- Anonymous March 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

int getsize(int* r) {
  if (r[0] <= r[1]) {
    if (r[2] <= r[0]) return r[1]-r[2];
    else if (r[2] <= r[1]) return r[1]-r[0];
    return r[2]-r[0];
  }
  if (r[2] <= r[1]) return r[0]-r[2];
  else if (r[2] <= r[0]) return r[0]-r[1];
  return r[2]-r[1];
}

int main(void) {
  int a[] = { 0, 9, 12, 20 };
  int b[] = { 4, 10, 15, 24, 26 };
  int c[] = { 5, 18, 22, 30 };
  int la = 4, lb = 5, lc = 4;
  int minrange[3] = { a[0], b[0], c[0] };
  int minsize = getsize(minrange);
  int ia = 1, ib = 1, ic = 1;
  int currrange[3] = { a[0], b[0], c[0] };
  while (ia < la || ib < lb || ic < lc) {
    int x = 1000;
    int xid = -1;
    if (ia < la) { x = a[ia]; xid = 0; }
    if (ib < lb && b[ib] < x) { x = b[ib]; xid = 1; }
    if (ic < lc && c[ic] < x) { x = c[ic]; xid = 2; }
    currrange[xid] = x;
    int currsize = getsize(currrange);
    if (currsize < minsize) {
      minrange[0] = currrange[0];
      minrange[1] = currrange[1];
      minrange[2] = currrange[2];
      minsize = currsize;
    }
    if (xid == 0) ia++;
    else if (xid == 1) ib++;
    else ic++;
  }
  printf("%d %d %d\n", minrange[0], minrange[1], minrange[2]);
  printf("%d\n", minsize);
  return 0;
}

- song May 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

int getsize(int* r) {
  if (r[0] <= r[1]) {
    if (r[2] <= r[0]) return r[1]-r[2];
    else if (r[2] <= r[1]) return r[1]-r[0];
    return r[2]-r[0];
  }
  if (r[2] <= r[1]) return r[0]-r[2];
  else if (r[2] <= r[0]) return r[0]-r[1];
  return r[2]-r[1];
}

int main(void) {
  int a[] = { 0, 9, 12, 20 };
  int b[] = { 4, 10, 15, 24, 26 };
  int c[] = { 5, 18, 22, 30 };
  int la = 4, lb = 5, lc = 4;
  int minrange[3] = { a[0], b[0], c[0] };
  int minsize = getsize(minrange);
  int ia = 1, ib = 1, ic = 1;
  int currrange[3] = { a[0], b[0], c[0] };
  while (ia < la || ib < lb || ic < lc) {
    int x = 1000;
    int xid = -1;
    if (ia < la) { x = a[ia]; xid = 0; }
    if (ib < lb && b[ib] < x) { x = b[ib]; xid = 1; }
    if (ic < lc && c[ic] < x) { x = c[ic]; xid = 2; }
    currrange[xid] = x;
    int currsize = getsize(currrange);
    if (currsize < minsize) {
      minrange[0] = currrange[0];
      minrange[1] = currrange[1];
      minrange[2] = currrange[2];
      minsize = currsize;
    }
    if (xid == 0) ia++;
    else if (xid == 1) ib++;
    else ic++;
  }
  printf("%d %d %d\n", minrange[0], minrange[1], minrange[2]);
  printf("%d\n", minsize);
  return 0;
}

- song May 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The cleanest solution posted ever :

struct cell{
	int val;
	int ind1;
	int ind2;
	cell(int val, int ind1=0, int ind2=0):val(val),ind1(ind1),ind2(ind2){}
	bool operator<(const cell& before) const  {
		return this->val > before.val;
	}
};

int getMin(vector<int>& r) {
	int minV=INT_MAX;
	for(int i=0; i<r.size(); ++i)    minV=min(minV, r[i]);
	return minV;
}
int getMax(vector<int>& r) {
	int maxV=INT_MIN;
	for(int i=0; i<r.size(); ++i)   maxV=max(maxV, r[i]);
	return maxV;
}

void findMinRange(vector<vector<int>>& range, vector<int>& min_range) {
	priority_queue<cell> q;
	for(int i=0; i<range.size(); ++i) {
		q.push(cell(range[i][0], i, 0));
		min_range.push_back(range[i][0]);
	}
	int min_diff=getMax(min_range)-getMin(min_range);
	vector<int> r=min_range;
	while(true) {
		cell c=q.top();
		q.pop();
		if(range[c.ind1].size()-1 == c.ind2) break;
		q.push(cell(range[c.ind1][c.ind2+1], c.ind1, c.ind2+1));
		r[c.ind1]=range[c.ind1][c.ind2+1];
		int diff=getMax(r)-getMin(r);
		if(diff < min_diff){
			min_range=r;
			min_diff=diff;
		}		
	}
}

- jigili September 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

cleanest solution ever:

struct cell{
	int val;
	int ind1;
	int ind2;
	cell(int val, int ind1=0, int ind2=0):val(val),ind1(ind1),ind2(ind2){}
	bool operator<(const cell& before) const  {
		return this->val > before.val;
	}
};

int getMin(vector<int>& r) {
	int minV=INT_MAX;
	for(int i=0; i<r.size(); ++i)
		minV=min(minV, r[i]);
	return minV;
}
int getMax(vector<int>& r) {
	int maxV=INT_MIN;
	for(int i=0; i<r.size(); ++i)
		maxV=max(maxV, r[i]);
	return maxV;
}

void findMinRange(vector<vector<int>>& range, vector<int>& min_range) {
	priority_queue<cell> q;
	for(int i=0; i<range.size(); ++i) {
		q.push(cell(range[i][0], i, 0));
		min_range.push_back(range[i][0]);
	}
	int min_diff=getMax(min_range)-getMin(min_range);
	vector<int> r=min_range;
	while(true) {
		cell c=q.top();
		q.pop();
		if(range[c.ind1].size()-1 == c.ind2) break;
		q.push(cell(range[c.ind1][c.ind2+1], c.ind1, c.ind2+1));
		r[c.ind1]=range[c.ind1][c.ind2+1];
		int diff=getMax(r)-getMin(r);
		if(diff < min_diff){
			min_range=r;
			min_diff=diff;
		}		
	}
}

- jigili September 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python Version

import sys

input = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]

k = len(input)

counter = [0] * k



def permutations():
    minRange = []
    while True:
        group = []
        for i, t in enumerate(counter):
            group.append(input[i][t])

        group.sort()
        if len(minRange) == 0:
            minRange = group
        elif (group[k - 1] - group[0]) < (minRange[k - 1] - minRange[0]):
            minRange = group

        i = 0
        while i < len(counter):
            counter[i] += 1
            if counter[i] == len(input[i]):
                counter[i] = 0
                i += 1
                if i == len(counter):
                    print(minRange)
                    return
            else:
                break

permutations()

- om471987 September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Javascript brute force method

var a = [4, 10, 15, 24, 26];
var b = [0, 9, 12, 20];
var c = [5, 18, 22, 30];

function arrayIncludesRange(array, min, max) {
  for (var i in array) {
    var num = array[i];
    if (num >= min && num <= max) return true;
  }
  return false;
}

function includesEachArray(arrays, min, max) {
  for (var i in arrays) {
    var arr = arrays[i];
    if (!arrayIncludesRange(arr, min, max)) return false;
  }
  return true;
}

function largestRange(arrays) {
  var result = [Infinity, -Infinity];
  for (var i in arrays) {
    var arr = arrays[i];
    result[0] = Math.min(arr[0], result[0]);
    result[1] = Math.max(arr[arr.length-1], result[1]);
  }
  return result;
}

function smalliestRange() {
  var range = largestRange(arguments);
  var largestMax = range[1];
  var largestDelta = range[1] - range[0];
  
  for (
    var currentDelta = 0;
    currentDelta <= largestDelta;
    currentDelta++) {
    for (
      var currentMin = range[0], currentMax = range[0] + currentDelta;
      currentMax <= largestMax;
      ++currentMin && (currentMax = currentMin + currentDelta)) {
      if (includesEachArray(arguments, currentMin, currentMax)) {
        return [currentMin, currentMax];
      }
    }
  }
  return range;
}

var output = smalliestRange(a, b, c);
console.log(output);

- cody September 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution is to combine the k lists into one list with the added info of index of the original list (srcK in the code) then sort the combined list. Once we have the sorted combined list, we just need to iterate through the list and use the source K to point to the current value for update. Complexity is O(N logN). Python code below:

import random

# generate random data for testing
k = 5
ll = [[]] * k
random.seed(1)
for iK in range(k):
	ll[iK] = sorted([random.randint(1, 99) for x in range(random.randint(5,10))])
	print ll[iK]
	
# test data, 3 lists
# ll[0] = [4, 10, 15, 24, 26]
# ll[1] = [0,9,12,20]
# ll[2] = [5,18,19, 22, 30]
#k = len(ll)

combLl = []
for iK in range(k):
	combLl.extend([(iK,x) for x in ll[iK]])
	
combLl.sort(key=lambda x: x[1] )
srcK, v = zip(*combLl)

curV = [0]*k
for iK in range(k):
	curV[iK] = ll[iK][0]
minRange = max(curV) - min(curV)
minV = curV[:]
iComb = max([s.index(iK) for iK in range(k)])
iComb += 1
while  iComb < len(v):
	iK = srcK[iComb];
	curV[iK] = v[iComb] 
	rangeV  = curV[iK] - min(curV)
	if rangeV < minRange:
		minRange = rangeV
		minV = curV[:]
	
	iComb +=1
print "Final Min:", minRange,  minV

- Adchen22 September 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution is of O(k*log(k)) complexity
I will call the smallest side of sorted lists the left side, and the greatest side the right side:
1.Get only the greatest and smallest of all k lists and discard all other elements, now we have k lists with at most 2 elements.
2. Merge these sorted lists and in the process create an equal size array(actually a bit field will be enough, we only need two values) to record for each element of the same index in the resulting merge array, whether this element was the left side or the right side of one of the k lists.
3. From the left side, proceed right until one element that was one of the original k lists' right side is reached. This element will mark the left side of the desired range.
4. Repeat 3. from the right side; and obtain the right side of the desired range.
Complexity discussion:
step 1. is O(1), in step 2., Merging of elements of total size at most 2*k, therefore O(k*log(k)). Step 3. and 4. combined take less than 2k looping.

- zFaust September 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution is of O(k*log k) complexity
I will call the least side of a sorted list the left side and the greatest side the right side
1. take only the min and max of every list and discard all other elements, now we have k lists each of size at most 2.
2. Merge these lists to form list L and meanwhile create an array A of equal size(indeed this can be a bit field, for we only need two values for each entry); during the forming of list L, for every element of L, record in corresponding index of A whether this element was the min or max of the original k lists.
3. Starting from the left side of L, proceed right one by one until an element that is the right side of one of the original k list is reached, this can be verified by indexing A. This element will mark the left side of the desired range.
4. Repeat step 3. from the right side of L. And obtain the right side of the desired range.
Comlexity:
step 1 is of O(1), step 3. and 4. combined will not take more than 2*k looping. Step 2. is the merging of less than 2*k elements and thus O(k*log(k))

- zFaust September 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The answer can easily be found in linear time.

min_range = (minimum of all range.end)
max_range = if (maximum of all range.begin) > min_range ? (maximum of all range.begin) : (the next number in all ranges after min_range).

The time complexity is depending on input: O(number of ranges) or O(total number of elements in all the ranges)

- gigilibala October 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution on JavaScript. Algorythm is following: go throw all values from min to max, assume it's the left border of the range, and look for a right one. Store the best options and return it as a result;

function getSmallestRange(lines){
	var k = lines.length;
	var currentIndexes = [];
	for(var i=0; i<k; i++) 
	{
		currentIndexes[i]=0;
	}

	var minRangeSize=-1;
	var minRangeLeft=0;
	var minRangeRight=0;

	var minLine;
	while((minLine = getLineWithMinValue(lines, currentIndexes)) >= 0){
		var rangeRight = getRangeRight(lines, currentIndexes);	
		var rangeLeft = lines[minLine][currentIndexes[minLine]];
		rangeSize = rangeRight - rangeLeft;

		if(minRangeSize < 0 || rangeSize < minRangeSize){
			minRangeSize = rangeSize;
			minRangeLeft = rangeLeft;
			minRangeRight = rangeRight;		
		}
		currentIndexes[minLine]++;
	}
	
	if(minRangeSize < 0)
		return "not found";
	return "["+minRangeLeft + ", " + minRangeRight+"]";
}

function getRangeRight(lines, currentIndexes){
	var maxValue=0;
	var maxIndex=-1;
	for(var i=0; i<lines.length; i++){
		if(currentIndexes[i] < lines[i].length){
			var currentIndex = lines[i][currentIndexes[i]];			
			if(maxIndex<0 || currentIndex > maxValue){
				maxValue = currentIndex;
				maxIndex = i;
			}				
		}
	}
	return maxValue;
}

function getLineWithMinValue(lines, currentIndexes){
	var minIndex = -1;
	var minValue = 0;
	for(var i=0; i<lines.length; i++){
		if(currentIndexes[i] >= lines[i].length)
			return -1;
		if(minIndex < 0 || lines[i][currentIndexes[i]] < minValue){
			minIndex = i;
			minValue = lines[i][currentIndexes[i]];
		}
	}
	return minIndex;
}

- Maxim October 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import scala.annotation.tailrec
import scala.collection.mutable

object SmallestRange {
  def mergeSort(lists: List[List[(Int, Int)]]): List[(Int, Int)] = {
    val priorityQueue = mutable.PriorityQueue[(Int, Int)]().reverse
    priorityQueue.enqueue(lists.flatMap(_.headOption):_*)

    var result = List[(Int, Int)]()
    var lists2 = lists.map(_.tail)
    while(priorityQueue.nonEmpty) {
      val root = priorityQueue.dequeue()
      result = root :: result
      lists2(root._2) match {
        case (x :: xs) =>
          priorityQueue += x
          lists2 = lists2.updated(root._2, xs)
        case _ =>
      }
    }
    result.reverse
  }

  @tailrec
  def findInitialValues(mergedList: List[(Int, Int)], set: Set[Int], count: Int, result: List[Int]): (List[(Int, Int)], List[Int]) = {
    if(set.size >= count) {
      return (mergedList, result)
    }

    val first = mergedList.head
    val processedLists = set + first._2
    val newResult = result.updated(first._2, first._1)
    findInitialValues(mergedList.tail, processedLists, count, newResult)
  }

  def findMinimum(mergedList: List[(Int, Int)], count: Int): List[Int] = {
    @tailrec
    def go(list: List[(Int, Int)], values: List[Int], minRange: Int, minValues: List[Int]): List[Int] = {
      list match {
        case Nil => minValues
        case ((v, idx) :: xs) =>
          val newMinValues = values.updated(idx, v)
          val newMinRange = newMinValues.max - newMinValues.min
          if(newMinRange < minRange) {
            go(xs, newMinValues, newMinRange, newMinValues)
          } else {
            go(xs, newMinValues, minRange, minValues)
          }
      }
    }

    val (leftMergedList, initialValues) = findInitialValues(mergedList, Set[Int](), count, List.fill(count)(0))
    go(leftMergedList, initialValues, Integer.MAX_VALUE, initialValues)
  }

  def main(args: Array[String]): Unit = {
    val lists = List(
      List(4, 10, 15, 24, 26),
      List(0, 9, 12, 20),
      List(5, 18, 22, 30)
    )

    val indexedValues = lists.zipWithIndex
      .map{ case (l, i) => l.map((_, i)) }
    val mergedList = mergeSort(indexedValues)

    val min = findMinimum(mergedList, lists.size)
    println(min)
  }
}

- A V December 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import scala.annotation.tailrec
import scala.collection.mutable

object SmallestRange {
  def mergeSort(lists: List[List[(Int, Int)]]): List[(Int, Int)] = {
    val priorityQueue = mutable.PriorityQueue[(Int, Int)]().reverse
    priorityQueue.enqueue(lists.flatMap(_.headOption):_*)

    var result = List[(Int, Int)]()
    var lists2 = lists.map(_.tail)
    while(priorityQueue.nonEmpty) {
      val root = priorityQueue.dequeue()
      result = root :: result
      lists2(root._2) match {
        case (x :: xs) =>
          priorityQueue += x
          lists2 = lists2.updated(root._2, xs)
        case _ =>
      }
    }
    result.reverse
  }

  @tailrec
  def findInitialValues(mergedList: List[(Int, Int)], set: Set[Int], count: Int, result: List[Int]): (List[(Int, Int)], List[Int]) = {
    if(set.size >= count) {
      return (mergedList, result)
    }

    val first = mergedList.head
    val processedLists = set + first._2
    val newResult = result.updated(first._2, first._1)
    findInitialValues(mergedList.tail, processedLists, count, newResult)
  }

  def findMinimum(mergedList: List[(Int, Int)], count: Int): List[Int] = {
    @tailrec
    def go(list: List[(Int, Int)], values: List[Int], minRange: Int, minValues: List[Int]): List[Int] = {
      list match {
        case Nil => minValues
        case ((v, idx) :: xs) =>
          val newMinValues = values.updated(idx, v)
          val newMinRange = newMinValues.max - newMinValues.min
          if(newMinRange < minRange) {
            go(xs, newMinValues, newMinRange, newMinValues)
          } else {
            go(xs, newMinValues, minRange, minValues)
          }
      }
    }

    val (leftMergedList, initialValues) = findInitialValues(mergedList, Set[Int](), count, List.fill(count)(0))
    go(leftMergedList, initialValues, Integer.MAX_VALUE, initialValues)
  }

  def main(args: Array[String]): Unit = {
    val lists = List(
      List(4, 10, 15, 24, 26),
      List(0, 9, 12, 20),
      List(5, 18, 22, 30)
    )

    val indexedValues = lists.zipWithIndex
      .map{ case (l, i) => l.map((_, i)) }
    val mergedList = mergeSort(indexedValues)

    val min = findMinimum(mergedList, lists.size)
    println(min)
  }
}

- Akmo December 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Below is a my solution of this problem. Here i used three method

1. combineSortedArray : it is just to combine all the arrays and perform sorting on it.

2. isCoverAllArrayCount : is just to check our selected array contains at least one digit from all arrays.

3. calculateMinDistance this is our main logic method. It contacts main logic for this algorithm

import java.util.Set;
  import java.util.TreeSet;

  public class LengthOfArray {

  	public static void main(String args[]) {

  		int[][] arrayOfArray = { { 2, 10, 15, 24, 26 }, { 0, 1, 9, 12, 20 }, { 3, 4, 18, 22, 30 } };
  		int[] selectedArray = calculateMinDistance(arrayOfArray);

  		System.out.print("[ ");
  		for (int i : selectedArray) {
  			System.out.print(i + " ");
  		}
  		System.out.println("]");

  	}

  	private static int[] calculateMinDistance(int[][] arrays) {

  		Integer arrayOfSet[] = combineSortedArray(arrays);

  		int minRangeFoundForSelectedArray = arrayOfSet[arrayOfSet.length - 1] - arrayOfSet[0];
  		int arrayLength = arrays.length;
  		int selectedArray[] = new int[arrayLength];
  		int validCount = (arrayLength) * (arrayLength + 1) / 2;

  		int count = 0;
  		while ((count + arrayLength) < arrayOfSet.length) {

  			int[] tempArray = new int[arrayLength];
  			for (int i = 0; i < arrayLength; i++) {
  				tempArray[i] = arrayOfSet[i + count];
  			}
  			if (((tempArray[arrayLength - 1] - tempArray[0]) <= minRangeFoundForSelectedArray)
  					&& isCoverAllArrayCount(tempArray, arrays) == validCount) {
  				selectedArray = tempArray;
  				minRangeFoundForSelectedArray = tempArray[arrayLength - 1] - tempArray[0];
  			}
  			count++;
  		}

  		return selectedArray;
  	}

  	private static int isCoverAllArrayCount(int[] selectedArray, int[][] arrays) {
  		int count = 0;

  		for (int i = 0; i < arrays.length; i++) {
  			int[] singleArray = arrays[i];
  			loopJ: for (int j : singleArray) {
  				for (int selectedInt : selectedArray) {
  					if (j == selectedInt) {
  						count += i + 1;
  						break loopJ;
  					}
  				}
  			}
  		}

  		return count;
  	}

  	private static Integer[] combineSortedArray(int arrays[][]) {
  		Set<Integer> set = new TreeSet<Integer>();

  		for (int[] a : arrays) {
  			for (int number : a) {
  				set.add(number);
  			}
  		}

  		Integer arrayOfSet[] = set.toArray(new Integer[set.size()]);
  		return arrayOfSet;
  	}

  }

- dhiralpandya March 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
int main() {
	std::vector<std::vector<int>> ls {{4, 10, 15, 24, 26},
		{0, 9, 12, 20},
		{5, 18, 22, 30}
	};

	std::vector<int> idxs(3, 0);
	int done = 0, delta = numeric_limits<int>::max();
	int best_lo = numeric_limits<int>::min()/10;
	int best_hi = numeric_limits<int>::max()/10;

	while (true) {
		int minidx = -1;
		int minval = numeric_limits<int>::max(); 
		int lo = numeric_limits<int>::max();
		int hi = numeric_limits<int>::min();
		for (auto i = 0; i < idxs.size(); i++) {
			lo = min(lo, ls[i][idxs[i]]);
			hi = max(hi, ls[i][idxs[i]]);
			if (idxs[i] < ls[i].size() && ls[i][idxs[i]] < minval) {
				minval = ls[i][idxs[i]];
				minidx = i;
			}
		}
		if (minidx == -1)
			break;
		if (hi - lo < best_hi - best_lo) {
			best_hi = hi;
			best_lo = lo;
		}
		idxs[minidx]++;
	}
	cout << "range: [" << best_lo << ", " << best_hi << "]\n";
}

- meself April 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

min(int a, int b, int c) {
if ( a <= b && a <= c ) return a;
if ( b <= a && b <= c ) return b;
return c;
}


max(int a, int b, int c) {
if ( a <= b && a <= c ) return a;
if ( b <= a && b <= c ) return b;
return c;
}


int findMin(List l1, List l2, List l3) {
int i1 = 1;
int i2 = 1;
int i3 = 1;
int a = l1.get(0);
int b = l1.get(0);
int c = l1.get(0);
while ( i1 != l1.size() && i2 != l2.size() && i3 != l3.size() ) {
best = Math.min( best, max(a,b,c) - min(a,b,c) );
int m = min(a,b,c);
if ( l1.get(i-1) == m ) {
a = l1.get(i1);
i1++;
} else if (l2.get(i2 - 1) == m) {
b = l2.get(i1);
i2++;
} else {
c = l3.get(i3);
i3++;
}
}

return best;
}

- gime July 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def get_range(matrix):
    lt = []
    for i in range(len(matrix)):
        lt += map(lambda x: (x, i), matrix[i])
    lt = sorted(lt, key=lambda x: x[0])
    set_size = len(matrix)
    min_range = float("+infinity")
    result = []
    for i in range(len(lt)):
        s = set()
        for j in range(i, len(lt)):
            s.add(lt[j][1])
            if len(s) == set_size:
                r = lt[j][0] - lt[i][0]
                min_range = min([r, min_range])
                result = lt[i:j+1]
                break
    return result

- tkachoff July 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find the range ($min - $max) of the smallest values in each list, remove the smallest value(s) and repeat. There's no better range that begins with $min, so if we haven't found the best range yet, then the best must begin with a higher value. Code, debug output and test case in Perl:

#!/usr/bin/env perl
use v5.018;
use warnings;
use List::Util qw(min max);
use Test::More;

my @list = (
  [4, 10, 15, 24, 26],
  [0, 9, 12, 20],
  [5, 18, 22, 30],
);

my $range; # Difference between high and low
my $low;
my $high;
while () {
  my @mins = map { last unless defined $_->[0]; $_->[0] } @list;
  my $min = min(@mins);
  my $max = max(@mins);
  my $diff = $max - $min;
  if (!defined $range || $diff < $range) {
    $range = $diff;
    ($low, $high) = ($min, $max)
  }

  # Remove min(s)
  map { shift $_ if $_->[0] == $min } @list;
  say "Found Range $min - $max ($diff)";
}
say "Best Range: $low - $high ($range)";

is($low, 20, 'Low is 20');
is($high, 24, 'High is 24');
done_testing;

- perlrocks October 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find the range ($min - $max) of the smallest values in each list, remove the smallest value(s) and repeat. There's no better range that begins with $min, so if we haven't found the best range yet, then the best must begin with a higher value. Code, debug lines and test case in Perl:

#!/usr/bin/env perl
use v5.018;
use warnings;
use List::Util qw(min max);
use Test::More;

my @list = (
  [4, 10, 15, 24, 26],
  [0, 9, 12, 20],
  [5, 18, 22, 30],
);

my $range; # Difference between high and low
my $low;
my $high;
while () {
  my @mins = map { last unless defined $_->[0]; $_->[0] } @list;
  my $min = min(@mins);
  my $max = max(@mins);
  my $diff = $max - $min;
  if (!defined $range || $diff < $range) {
    $range = $diff;
    ($low, $high) = ($min, $max)
  }

  # Remove min(s)
  map { shift $_ if $_->[0] == $min } @list;
  say "Found Range $min - $max ($diff)";
}
say "Best Range: $low - $high ($range)";

is($low, 20, 'Low is 20');
is($high, 24, 'High is 24');
done_testing;

- perlrocks October 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a liniar solution when the number of lists k is much smaller than the sizes of the largests lists.

This solution is O(kn) where n is the size of largest list and k is the number of lists.

Essentially we maintain a list of pointers starting at the beginning of the list. Because they are already in sorted order, we can just increment the pointer of the list with the current smallest element. As we loop through the lists we keep track of the range and if its the smallest one we've seen so far we remember it. Once all the pointers are at the end of their respective lists we finish and return the smallest range.

We also only use O(k) space.

def smallest_range(lists)
  pointers = [0] * lists.size

  remaining_lists = Array.new
  for i in (0...lists.size)
    remaining_lists << i
  end

  smallest_range_size = nil
  smallest_range_first = nil
  smallest_range_last = nil

  while remaining_lists.count > 0
    numbers = (0...lists.size).map { |i| lists[i][pointers[i]] }

    small = numbers.min
    large = numbers.max
    range = large - small

    if smallest_range_size.nil? || smallest_range_size > range
      smallest_range_size = range
      smallest_range_first = small
      smallest_range_last = large
    end

    # Increment pointer of list in remaining list with current smallest number
    smallest_list = remaining_lists.first
    smallest_list_number = lists[0][pointers[0]]
    remaining_lists.each do |r|
      num = lists[r][pointers[r]]
      if num <= smallest_list_number
        smallest_list_number = num
        smallest_list = r 
      end
    end
    if pointers[smallest_list] >= lists[smallest_list].size - 1
      remaining_lists.delete(smallest_list)
    else
      pointers[smallest_list] += 1
    end
  end

  return [smallest_range_first, smallest_range_last]
end

- mikearevell October 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

-Find min and max, compute the diff
-increment the min until we can't anymore
-return smallest diff

public class Solution {
    private List<Integer>[] lists;

    private class MinMax {
        private int min, max, diff;

        MinMax(int min, int max) {
            this.min = min;
            this.max = max;
            this.diff = this.max - this.min;
        }

        MinMax(MinMax minMax) {
            this(minMax.getMin(), minMax.getMax());
        }

        int getMin() {
            return min;
        }

        void setMinMax(int min, int max) {
            this.min = min;
            this.max = max;
            this.diff = max - min;
        }

        int getMax() {
            return max;
        }

        int getDiff() {
            return diff;
        }

        @Override
        public String toString() {
            return "[" + min + ", " + max + "], " + diff;
        }
    }

    public void getSmallestRange(List<Integer>... lists) {
        this.lists = lists;
        if (lists == null || lists.length <= 1) {
            System.out.println("[] " + 0);
            return;
        }
        MinMax minMax = getMinMax();
        //One  or more list is null return 0
        if (minMax == null) {
            System.out.println("[] " + 0);
            return;
        }
        MinMax tempMinMax = new MinMax(minMax);
        //increment the min of all lists until we can't anymore
        while (incrementMin(tempMinMax.getMin())) {
            tempMinMax = getMinMax();
            if (tempMinMax.getDiff() < minMax.getDiff()) {
                minMax.setMinMax(tempMinMax.getMin(), tempMinMax.getMax());
            }
        }
        System.out.println(minMax.toString());
    }

    private boolean incrementMin(int minus) {
        for (int i = 0; i < lists.length; i++) {
            if (lists[i].get(0) == minus) {
                lists[i].remove(0);
                if (lists[i].isEmpty()) {
                    return false;
                }
            }
        }
        return true;
    }

    public MinMax getMinMax() {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE, current;
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] == null) {
                return null;
            }
            current = lists[i].get(0);
            if (min > current) {
                min = current;
            }
            if (max < current) {
                max = current;
            }
        }
        return new MinMax(min, max);
    }

    public static void main(String[] s) {
        Solution solution = new Solution();
        List<Integer> l1 = new ArrayList<>(Arrays.asList(4, 10, 15, 24, 26));
        List<Integer> l2 = new ArrayList<>(Arrays.asList(0, 9, 12, 20));
        List<Integer> l3 = new ArrayList<>(Arrays.asList(5, 18, 22, 30));

        solution.getSmallestRange(l1, l2, l3);


    }
}

- jaban October 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// ZoomBA : Bad, elementary, declarative.
LL = [ [4, 10, 15, 24, 26] , 
   [0, 9, 12, 20] , 
   [5, 18, 22, 30] ]

range = reduce( LL ) -> { 
  min =  $.prev[0] ; max = $.prev[-1]
  if ( min > $.item[0] ){ min = $.item[0] }
  if ( max < $.item[-1] ){ max = $.item[-1] }
  [ min, max ]
}
r = [range.0 : range.1 + 1]
join ( r, r ) :: {
  #(min,max) = $.o // tuple 
  continue ( min > max )
  out_of_range = exists ( LL ) :: { 
    !exists( $.item ) :: { min <= $.item && $.item <= max } 
  }
  continue ( out_of_range || ( max - min > range.1 - range.0 ) )
  range.0 = min ; range.1 = max 
  false 
}
println( range )

- NoOne November 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MinDifference {

	public static void main(String args[]) {

		int[] list1 = { 4, 10, 15, 24, 26 };
		int[] list2 = { 0, 9, 12, 20 };
		int[] list3 = { 5, 18, 22, 30 };

		int list1Pointer = 0;
		int list2Pointer = 0;
		int list3Pointer = 0;

		int minSum = Integer.MAX_VALUE;
		int resultValueList1 = 0;
		int resultValueList2 = 0;
		int resultValueList3 = 0;

		while (true) {

			if (list1Pointer >= list1.length || list2Pointer >= list2.length
					|| list3Pointer >= list3.length) {
				break;
			}

			// Running Time O(1)
			int localMin = findMinDiff(list1[list1Pointer],
					list2[list2Pointer], list3[list3Pointer]);

			if (localMin < minSum) {
				minSum = localMin;
				resultValueList1 = list1[list1Pointer];
				resultValueList2 = list2[list2Pointer];
				resultValueList3 = list3[list3Pointer];
			}

			// Running Time O(1)
			int incrementList = findMinList(list1[list1Pointer],
					list2[list2Pointer], list3[list3Pointer]);
			if (incrementList == 1) {
				list1Pointer++;
			}
			if (incrementList == 2) {
				list2Pointer++;
			}
			if (incrementList == 3) {
				list3Pointer++;
			}

		}
		// Total running time O(n)
		System.out.println(resultValueList1 + " " + resultValueList2 + "  "
				+ resultValueList3);

	}

	// Running Time O(1)
	public static int findMinDiff(int a, int b, int c) {
		int min = 0;
		int max = 0;

		if (a > b) {

			min = b;
			max = a;

		} else {
			min = a;
			max = b;
		}
		if (c > max) {
			max = c;
		}
		if (c < min) {
			min = c;
		}
		return (max - min);
	}

	// Running Time O(1)
	public static int findMinList(int a, int b, int c) {
		int min = 0;
		if (a < b) {
			if (a < c) {
				min = 1;
			} else {
				min = 3;
			}

		} else {
			if (b < c) {
				min = 2;
			} else {
				min = 3;
			}
		}

		return min;
	}

}

- Amit Kumar November 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MinDifference {

public static void main(String args[]) {

int[] list1 = { 4, 10, 15, 24, 26 };
int[] list2 = { 0, 9, 12, 20 };
int[] list3 = { 5, 18, 22, 30 };

int list1Pointer = 0;
int list2Pointer = 0;
int list3Pointer = 0;

int minSum = Integer.MAX_VALUE;
int resultValueList1 = 0;
int resultValueList2 = 0;
int resultValueList3 = 0;

while (true) {

if (list1Pointer >= list1.length || list2Pointer >= list2.length
|| list3Pointer >= list3.length) {
break;
}

// Running Time O(1)
int localMin = findMinDiff(list1[list1Pointer],
list2[list2Pointer], list3[list3Pointer]);

if (localMin < minSum) {
minSum = localMin;
resultValueList1 = list1[list1Pointer];
resultValueList2 = list2[list2Pointer];
resultValueList3 = list3[list3Pointer];
}

// Running Time O(1)
int incrementList = findMinList(list1[list1Pointer],
list2[list2Pointer], list3[list3Pointer]);
if (incrementList == 1) {
list1Pointer++;
}
if (incrementList == 2) {
list2Pointer++;
}
if (incrementList == 3) {
list3Pointer++;
}

}
// Total running time O(n)
System.out.println(resultValueList1 + " " + resultValueList2 + " "
+ resultValueList3);

}

// Running Time O(1)
public static int findMinDiff(int a, int b, int c) {
int min = 0;
int max = 0;

if (a > b) {

min = b;
max = a;

} else {
min = a;
max = b;
}
if (c > max) {
max = c;
}
if (c < min) {
min = c;
}
return (max - min);
}

// Running Time O(1)
public static int findMinList(int a, int b, int c) {
int min = 0;
if (a < b) {
if (a < c) {
min = 1;
} else {
min = 3;
}

} else {
if (b < c) {
min = 2;
} else {
min = 3;
}
}

return min;
}

}

- Amit Kumar November 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MinDifference {

	public static void main(String args[]) {

		int[] list1 = { 4, 10, 15, 24, 26 };
		int[] list2 = { 0, 9, 12, 20 };
		int[] list3 = { 5, 18, 22, 30 };

		int list1Pointer = 0;
		int list2Pointer = 0;
		int list3Pointer = 0;

		int minSum = Integer.MAX_VALUE;
		int resultValueList1 = 0;
		int resultValueList2 = 0;
		int resultValueList3 = 0;

		while (true) {

			if (list1Pointer >= list1.length || list2Pointer >= list2.length
					|| list3Pointer >= list3.length) {
				break;
			}

			// Running Time O(1)
			int localMin = findMinDiff(list1[list1Pointer],
					list2[list2Pointer], list3[list3Pointer]);

			if (localMin < minSum) {
				minSum = localMin;
				resultValueList1 = list1[list1Pointer];
				resultValueList2 = list2[list2Pointer];
				resultValueList3 = list3[list3Pointer];
			}

			// Running Time O(1)
			int incrementList = findMinList(list1[list1Pointer],
					list2[list2Pointer], list3[list3Pointer]);
			if (incrementList == 1) {
				list1Pointer++;
			}
			if (incrementList == 2) {
				list2Pointer++;
			}
			if (incrementList == 3) {
				list3Pointer++;
			}

		}
		// Total running time O(n)
		System.out.println(resultValueList1 + " " + resultValueList2 + "  "
				+ resultValueList3);

	}

	// Running Time O(1)
	public static int findMinDiff(int a, int b, int c) {
		int min = 0;
		int max = 0;

		if (a > b) {

			min = b;
			max = a;

		} else {
			min = a;
			max = b;
		}
		if (c > max) {
			max = c;
		}
		if (c < min) {
			min = c;
		}
		return (max - min);
	}

	// Running Time O(1)
	public static int findMinList(int a, int b, int c) {
		int min = 0;
		if (a < b) {
			if (a < c) {
				min = 1;
			} else {
				min = 3;
			}

		} else {
			if (b < c) {
				min = 2;
			} else {
				min = 3;
			}
		}

		return min;
	}

}

- Amit Kumar November 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ Solution based on min heap

class Solution:{
    struct Compare{
        bool operator()(ListNode* a, ListNode* b){
            return a->val > b->val;
        }
    };
    
    pair<int,int> findMinRange(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Compare> min_heap;
        int start = 0, end = INT_MAX, maxV = 0;
        
        for(auto list : lists){
            if(list != NULL){
                min_heap.push(list);
                maxV = max(maxV, list->val);
            }
        }
        
        while(!min_heap.empty()){
            ListNode* temp = min_heap.top();
            min_heap.pop();
            
            if(end - start > maxV - temp->val){
                end = maxV;
                start = temp->val;
            }
            
            if(temp->next != NULL){
                min_heap.push(temp->next);
                maxV = max(maxV, temp->next->val);
            }
            else{
                break;
            }
        }
        return make_pair(start, end);
    }
};

- zequn2001 February 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def srange(l1, l2, l3):
	bl = [(i,1) for i in l1] + [(i, 2) for i in l2] + [(i,3) for i in l3]
	bl.sort(key=operator.itemgetter(0))
	best_range = None
	for index, (num, lst_index) in enumerate(bl, 1):
		nf = [1,2,3]
		nf.remove(lst_index)
		new_range = [num,]
		k = iter(bl[index:])
		while nf:
			try:
				next_num, next_index = k.next()
			except StopIteration:
				break
			new_range.append(next_num)
			if next_index in nf:
				nf.remove(next_index)
		if not nf:
			if not best_range or best_range[-1] - best_range[0] > new_range[-1] - new_range[0]:
				best_range = new_range
	return [best_range[0], best_range[-1]]

- adi May 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A C++ solution

This takes advantage of the pre-sorted nature (though an additional sort would only be required for lists 2 and 3, adding a (log(x) + log(y).) We loop only through list 1 (O(n)), find the closest values in lists 2 and 3 via binary search (log(x) + log(y)), and save the best min distance.

std::pair<int, int> getMinPair(
  const std::set<int>& set1,
  const std::set<int>& set2,
  const std::set<int>& set3)
{
  // Prepare the min distance return value
  std::pair<int, int> minDist(0, 0);
  
  // Save best min distance separately to avoid having to
  // constantly subtract the two minDist numbers
  int bestDist = INT_MAX;
  
  // Loop through each value in vector 1 - O(n)
  for (std::set<int>::const_iterator itr = set1.begin();
       itr != set1.end();
       ++itr)
  {
    // Find the closest values from itr to set2 and set3
    // via a binary search - nlog(x) + nlog(y)
    int x = getClosest(*itr, set2);
    int y = getClosest(*itr, set3);
    
    // Quickly sort the three values of interest
    std::set<int> sorted = {x, y, *itr};
    
    // Compare the distance
    int dist = *sorted.rbegin() - *sorted.begin();
    
    if (dist < bestDist)
    {
      // Save the new best distance
      bestDist = dist;
      minDist = std::make_pair(*sorted.begin(), *sorted.rbegin());
    }
  }
  
  return minDist;
}

Here's the helper method getClosest() which finds the closest value. A little verbose, but takes care of the edge cases.

int getClosest(int value, const std::set<int>& values)
{
  // We start by finding the lowerbound (which is >= value)
  // We then check the previous value (if exists) to see if
  // its closer than the lowerbound
  std::set<int>::const_iterator lb = values.lower_bound(value);
  
  // If we reached the end, the last value is the closest
  if (lb == values.end()) return *values.rbegin();
  
  // Check if we're at the first value
  if (lb == values.begin()) return *lb;
  
  // Compare the value with the previous in the list
  int lbVal = *lb;
  --lb;
  int prevVal = *lb;
  
  int lbDist   = lbVal   - value;
  int prevDist = prevVal - value;

  // Return the closer of the two  
  if (std::abs(prevDist) < std::abs(lbDist))
    return prevVal;

  return lbVal;
}

- Josh June 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

An ES6 Javascript solution making good use of the spread operator.

1. Since the lists are sorted, get the range of the first entries of each list
2. Drop the smallest value from the list with the smallest value
3. Repeat until any of the lists are empty.

let smallestRange = Infinity;
let range = [];

const findSmallestRange = (...arrays) => {
  while(Math.min(...arrays.map(arr => arr.length )) > 0) {
    range = getRange(arrays);
    const rangeLength = range[1] - range[0];
    smallestRange = rangeLength < smallestRange ? rangeLength : smallestRange;
    
    const dropNum = arrays.findIndex(arr => arr[0] === range[0]);
    arrays[dropNum] = arrays[dropNum].slice(1);
  }
  console.log(smallestRange, range);
};

const getRange = (arrays) => {
  const min = Math.min(...arrays.map(arr => arr[0]));
  const max = Math.max(...arrays.map(arr => arr[0]));
  return [min,max];
}

findSmallestRange(a1, a2, a3);

- matchai August 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If go through the lists taking the minimum number from each list gives the correct result. Probably there is room for optimization but the whole data set must be visited in any case.

class MinCommonRange {
    
    static int[] minNums(int[][] rows) {
        
        int bestMin = -1, bestMax = -1;
        int[] rowIndexes = new int[rows.length];
        
        while (true) {
         
            int minRow = -1;
            int min, max;
            min = max = rows[0][rowIndexes[0]];
            
            // Get min and max for current set
            for (int i = 0;i < rows.length;i++) {
                
                int[] row = rows[i];
                int rowIndex = rowIndexes[i];
                int num = row[rowIndex];
                
                if (num <= min) {
                    
                    // The lowest num which can be increased
                    if (rowIndex < row.length - 1) {
                        minRow = i;
                    }
                    
                    min = num;
                }
                else if (num > max) {
                    max = num;
                }
            }
            
            // The new best range
            if (bestMin < 0 || bestMax - bestMin > max - min) {
                bestMin = min;
                bestMax = max;
            }
            
            // End of numbers
            if (minRow < 0) {
                break;
            }
            
            rowIndexes[minRow]++;
        }
        
        return new int[] { bestMin, bestMax };
    }

	public static void main(String[] args) {
        int[] range = minNums(new int[][] {
            new int[] { 4, 10, 15, 24, 26 },
            new int[] { 0, 9, 12, 20 },
            new int[] { 5, 18, 22, 30 }
        });
        
        System.out.println("Range: " + range[0] + " to " + range[1]);
	}
}

- juha October 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

do anyone tell me what this code means

sequences = [[(item, n) for item in seq] for n, seq in enumerate(sequences)]

- Anirudh Singh November 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

time O(2^n) since we enumerate all permutations of k picks from the lists.
space O(k)

range :: [[Int]] -> ((Int,Int),[Int])
range lss =
  let
    bounds xs =
      let
        a =
          List.minimum xs
        b =
          List.maximum xs
      in
        (b-a,((b,a),xs))
    pick =
      fmap List.head . List.permutations
    picks =
      sequenceA . fmap pick $ lss
  in
    snd . List.minimumBy (comparing fst) . fmap bounds $
      [ xs | xs <- picks ]

- Maddie November 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this python code? The complexity should be O(k * m), where k=len(L) m=max([len(l) for l in L]).

def min_range(L):
    r_min = -float('inf')
    r_max = +float('inf')
    for l in L:
        r_min = max(r_min, l[0])
        r_max = min(r_max, l[-1])
    return [r_min, r_max]

- SamKChang March 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how about this?

def min_range(L):
    r_min = -float('inf')
    r_max = +float('inf')
    for l in L:
        r_min = max(r_min, l[0])
        r_max = min(r_max, l[-1])
    return [r_min, r_max]

- SamKChang March 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function smallRange(arr) {
  let minRange = Infinity;
  let minObj = [];
  const pos = arr.map(() => 0);
  const maxMoves = arr.map((iar) => iar.length).reduce((a,c) => a+c) - arr.length;
  for (let m = 0; m <= maxMoves; m++) {
    let currents = pos.map((p, i) => ar[ i ][ p ]);
    let min = Math.min.apply(this, currents);
    let max = Math.max.apply(this, currents);
    if (isNaN(min)) {
      break;
    }
    let range = max - min;
    if (range < minRange) {
      minRange = range;
      minObj = [ min, max ];
    }
    let stepUp = currents.indexOf(min);
    pos[ stepUp ]++;
  }
  return minObj;
}

- Anonymous November 02, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function smallRange(arr) {
  let minRange = Infinity;
  let minObj = [];
  const pos = arr.map(() => 0);
  const maxMoves = arr.map((iar) => iar.length).reduce((a,c) => a+c) - arr.length;
  for (let m = 0; m <= maxMoves; m++) {
    let currents = pos.map((p, i) => ar[ i ][ p ]);
    let min = Math.min.apply(this, currents);
    let max = Math.max.apply(this, currents);
    if (isNaN(min)) {
      break;
    }
    let range = max - min;
    if (range < minRange) {
      minRange = range;
      minObj = [ min, max ];
    }
    let stepUp = currents.indexOf(min);
    pos[ stepUp ]++;
  }
  return minObj;
}

- yairniz November 02, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**Given 3 numbers L1, L2 and L3 from list1, list2 and list3, the range will be calculated as
 range=max(L1,L2,L3)-min(L1,L2,L3)
 First we pick a number from list1, say list1[i]. 
 Given we have 3 lists (list1, list2 and list3) which are in order from smallest to biggest, 
 if list2[j] is the nearest smaller number than list1[i], 
 there's no need to go through numbers list2[j-1], list2[j-2] or any other smaller number 
 because list2[j-2]<list2[j-1]<list2[j]<list1[i] thus 
 the range between list1[i] and any given number list2[k] when k<j will result in a bigger range 
 than the range between list1[i] and list2[j].
        
 The same thought process can be made when comparing with bigger numbers than list1[i]. 
 If list2[j] is bigger than and the closest number to list1[i], 
 there's no need to go through any bigger numbers from list2 because 
 list1[i]<list2[j]<list2[j+1] thus when picking any number bigger than list2[j] 
 the range between this number and list1[i] will be bigger than the range between list1[i] and list2[j].
 This approach reduces the number of iterations significantly.
*/


import java.lang.Math;

public class findSmallestRange {
    public static void main(String args[]){
        int[] list1={4,10,15,24,26};
        int[] list2={0,9,12,20};
        int[] list3={5,18,22,30};
        range range = new range();
        range.setRange(list1[0],list2[0],list3[0]);
        range auxRange=new range();
        boolean bContinue;
        for(int i=0;i<list1.length;i++){
            for(int j=0;j<list2.length;j++){
                bContinue=true;
                if((j>0)&&(list2[j-1]>list1[i])){
                    bContinue=false;
                }
                if((j<list2.length-1)&&(list2[j+1]<list1[i])){
                    bContinue=false;
                }
                if(bContinue) for(int k=0;k<list3.length;k++){
                    auxRange.setRange(list1[i],list2[j],list3[k]);
                    if(auxRange.range<range.range){
                        range.setRange(list1[i],list2[j],list3[k]);
                    }
                }
            }
        }

        System.out.println("list1: "+range.list1);
        System.out.println("list2: "+range.list2);
        System.out.println("list3: "+range.list3);
        System.out.println("Range: "+range.range);
    }
}
class range{
    int list1,list2,list3;
    int min;
    int max;
    int range;
    void setRange(int i, int j, int k){
        list1=i;
        list2=j;
        list3=k;
        min=Math.min(Math.min(i,j),k);
        max=Math.max(Math.max(i,j),k);
        range=max-min;
    }

}

- Julian Fuentes November 15, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My Python solution:

from heapq import *
def get_sr(ls):
    z = ([(v,i) for v in l]
         for i,l in enumerate(ls))
    n = len(ls)
    last_seen = [[None, i] for i in range(n)]
    missing = (1 << n) - 1
    res = None
    for v,i in merge(*z):
        last_seen[i][0] = v
        if missing & (1 << i):
            missing ^= (1 << i)
            if not missing:
                left = min(last_seen)
                dist = v - left[0]
                if not res or dist < res[0]:
                    res = (dist, [left[0], v])
                missing |= (1 << left[1])
    return res[1]
    
ls = [[4, 10, 15, 24, 26], 
      [0, 9, 12, 20] ,
      [5, 18, 22, 30]]
print(get_sr(ls))

- adr October 18, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <limits>
#include <list>

std::list<int> smallest_containing_list(std::list<std::list<int>> lists){
	//Assuming lists is sorted
	//inefficient brute force first to just get it working
	int starting_num = 0;
	int end_num = std::numeric_limits<int>::max();
	bool found_greater;
	for(std::list<std::list<int>>::iterator it = lists.begin(); it != lists.end(); it++){
		for(std::list<int>::iterator it2 = (*it).begin(); it2 != (*it).end(); it2++){
			int max_of_closest_ints = (*it2);
			for(std::list<std::list<int>>::iterator it3 = lists.begin(); it3 != lists.end(); it3++){
				//ignores if same as starting list
				if(it3 == it){
					continue;
				}
				found_greater = false;
				for(std::list<int>::iterator it4 = (*it3).begin(); it4 != (*it3).end(); it4++){
					if((*it4) < (*it2)){
						continue;
					}else{
						found_greater = true;
						if((*it4) > max_of_closest_ints){
							max_of_closest_ints = (*it4);
						}
						break;
					}
				}
				//everything in another array is less than (*it2) / the current value to test as starting_num; since list is (TODO:presumably) sorted, everything further ahead iterating it2 to the end will have at least one other array where all the other values are smaller, so skip test
				if(!found_greater){
					break;
				}
			}
			if(!found_greater){
				break;
			}
			if(max_of_closest_ints - (*it2) < end_num - starting_num){
				end_num = max_of_closest_ints;
				starting_num = (*it2);
			}
		}
	}
	std::list<int> output;
	output.push_back(starting_num);
	output.push_back(end_num);
	return {starting_num, end_num};
}

int main(){
	std::list<int> a({4, 10, 15, 24, 26});
	std::list<int> b({0, 9, 12, 20});
	std::list<int> c({5, 18, 22, 30});
	/*std::list<int> a({1, 2, 3, 80});
	std::list<int> b({1, 2, 3, 90, 200});
	std::list<int> c({1, 2, 3, 99, 300});*/
	std::list<std::list<int>> d({a, b, c});
	std::list<int> result = smallest_containing_list(d);
	for(std::list<int>::iterator it = result.begin(); it != result.end(); it++){
	    std::cout << (*it) << std::endl;
	}
}

- zty3075 March 23, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

def minRange(a, b, c):
    mr = sys.maxint
    i = j = k = 0
    while i < len(a) and j < len(b) and k < len(c):
        cMax, cMin = max(a[i], b[j], c[k]), min(a[i], b[j], c[k])
        range = cMax - cMin
        if range < mr:
            mr = range
        i, j, k = i + (cMin in a), j + (cMin in b), k + (cMin in c)
    return mr

- Rock April 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

A C++ solution

Taking advantage of the sorted nature of the three lists, we just loop through the first list (O(n)), and use a binary search to find the closest value in the second and third lists (log(x) + log(y)). The best min distance is saved as necessary.

std::pair<int, int> getMinPair(
  const std::set<int>& set1,
  const std::set<int>& set2,
  const std::set<int>& set3)
{
  // Prepare the min distance return value
  std::pair<int, int> minDist(0, 0);
  
  // Save best min distance separately to avoid having to
  // constantly subtract the two minDist numbers
  int bestDist = INT_MAX;
  
  // Loop through each value in vector 1 - O(n)
  for (std::set<int>::const_iterator itr = set1.begin();
       itr != set1.end();
       ++itr)
  {
    // Find the closest values from itr to set2 and set3
    // via a binary search - nlog(x) + nlog(y)
    int x = getClosest(*itr, set2);
    int y = getClosest(*itr, set3);
    
    // Quickly sort the three values of interest
    std::set<int> sorted = {x, y, *itr};
    
    // Compare the distance
    int dist = *sorted.rbegin() - *sorted.begin();
    
    if (dist < bestDist)
    {
      // Save the new best distance
      bestDist = dist;
      minDist = std::make_pair(*sorted.begin(), *sorted.rbegin());
    }
  }
  
  return minDist;
}

Here's the helper method that does the binary search for getClosest(). A little verbose, but covers the edge cases.

int getClosest(int value, const std::set<int>& values)
{
  // We start by finding the lowerbound (which is >= value)
  // We then check the previous value (if exists) to see if
  // its closer than the lowerbound
  std::set<int>::const_iterator lb = values.lower_bound(value);
  
  // If we reached the end, the last value is the closest
  if (lb == values.end()) return *values.rbegin();
  
  // Check if we're at the first value
  if (lb == values.begin()) return *lb;
  
  // Compare the value with the previous in the list
  int lbVal = *lb;
  --lb;
  int prevVal = *lb;
  
  int lbDist   = lbVal   - value;
  int prevDist = prevVal - value;

  // Return the closer of the two  
  if (std::abs(prevDist) < std::abs(lbDist))
    return prevVal;

  return lbVal;
}

- Anonymous June 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

1)Find the minimum of all list's last index
List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]
which is 20 from List 2, take it as lower range.
2)Binary search in List 1 and List 3, and find its immediate greater value, which is 24 in List 1, and 22 in List 3.
3)Take the maximum of these two values as upper range(Which is 24).
4)Hence [20-24] is the required range.

- Anonymous April 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

1)Find the minimum of all list's last index
List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]
which is 20 from List 2, take it as lower range.
2)Binary search in List 1 and List 3, and find its immediate greater value, which is 24 in List 1, and 22 in List 3.
3)Take the maximum of these two values as upper range(Which is 24).
4)Hence [20-24] is the required range.
Kindly correct me, if i am wrong.

- prity April 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if the lists are as following?
List 1: [1, 2, 3, 80]
List 2: [1, 2, 3, 90, 200]
List 2: [1, 2, 3, 99, 300]

In that case, your algorithm chooses [80, 99]. the range is 99-80 = 19.
However the answer is [1, 2] where range is 1 ; i.e. 2-1.

that is why your algorithm won't work.

- impala May 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

I've not gone through all the solutions here but, but the ones I have gone through seem to be doing unnecessary things.
Here's my solution, feel free to point out the error:

Find the minimum element from the list of last elements in each list.
[20,26,30] minimum is 20.
You can bet that 20 is the start of that smallest range (Range that we seek).

Now just find out the next element in the all other lists that are bigger than 20.
Candidates are [22, 24]
Maximum of this [22, 24] is the end of the smallest range.

so answer becomes [22, 24].

This is how you make use of the fact that lists are sorted already

- wanderer April 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thank you! I was going crazy as to why this solution wasn't listed here. Running time is O(log n) I guess, where n is the size of the largest list.

- Anonymous May 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

What happens if the lists are these?
List 1: [1, 10, 15, 24, 26]
List 2: [0, 9, 12, 18]
List 3: [2, 18, 22, 30]

The smallest range should be [0, 2], while your algorithm would return [18, 24] right?

- Sunny June 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

We do not need to start from the beginning, as suggested here. Instead, start at tails. The smallest of the tails is the lower bound of the range guaranteed. The issue is to find the upper bound. Of course the upper bound cannot be more than the max of all tails.

So start with the max of tails as upper bound. To best this estimation, compare the next smaller number than this tail (in the same list as the max of tails, of course). If this number is greater than lower bound (which is fixed), then continue looking. Stop when your number is smaller than lower bound.

This way, you don't need search all the K lists. Here is the pseudo code:

For each list in K collection:
	Get the tailValue and eval the running minimum (minOfTails)
	Get the tailValue and eval the running maximum (maxOfTails)
:loop end

Set the range lower bound = minOfTails //This is our lower bound

//Now take the Kth list whose tail is maximum
For each item in the Kth list: (reverse loop, from the tail)
         Check: If minOfTails is less than the element
         If yes, continue
         If no, then set the element as upper bound of range and exit
:loop end
Set the last known KList value greater than minOfTails as upper bound of range.

- whitenoise April 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Just simple O(N) space and O(N) time can work.
1. Merge these array into one in O(N) time,
2. Initial two pointer L,R to cover first K minimum numbers.
4. Calculate the "Range".
3. Delete pointer L's number which belong to X array(we suppose), move R to right until meet a number also belong to X array.
5. repeat 3-4 until R beyond range

It's the idea of "window move". And it's O(N) time.

- Prowindy October 04, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More