Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
since the input lists are already sorted, we should take advantage of it rather than creating a new minHeap.
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.
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
Nice solution only one thing is missing which is how to make use of sorted nature of lists as rightly pointed by @Vinod K
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;
}
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?
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;
}
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"
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;
}
}
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.
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]
This is the same as: merge all the N lists into one long array, then keep a sliding window of N.
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
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.
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);
}
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;
}
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.
Correct....
no doubt sol is fantastic..... I like the way of presenting your sol.... great job...
#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;
}
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 - 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)
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.
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.
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.
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.
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.
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).
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.
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).
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).
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
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;
}
}
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.
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.
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!
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?
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.
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
#!/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.
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;
}
}
}
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;
}
}
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;
}
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;
}
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";
}
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]
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);
}
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;
}
}
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;
}
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
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));
}
}
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]
]));
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;
}
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);
}
}
}
}
}
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;
}
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.
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
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());
}
/*
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
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
#!/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)
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
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
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;
}
#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;
}
#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;
}
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;
}
}
}
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;
}
}
}
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()
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);
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
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.
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))
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)
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;
}
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)
}
}
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)
}
}
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;
}
}
#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";
}
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;
}
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
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;
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;
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
-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);
}
}
// 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 )
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;
}
}
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;
}
}
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;
}
}
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);
}
};
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]]
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;
}
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);
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]);
}
}
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 ]
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;
}
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;
}
/**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;
}
}
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))
#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;
}
}
def findSmallestRange(a,b,c):
i,j,k = 0,0,0
srange = None
while i < len(a) and j < len(b) and k < len(c):
beg = min(a[i],b[j],c[k])
end = max(a[i],b[j],c[k])
if a[i] == beg: i += 1
if b[j] == beg: j += 1
if c[k] == beg: k += 1
if srange == None or end-beg < srange[1] - srange[0]:
srange = [beg,end]
return srange
Here is my full java solution:
public class MinRangeInKSortedList {
/**
* Problem Statement:
* You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.
* <p>
* For example,
* List 1: [4, 10, 15, 24, 26]
* List 2: [0, 9, 12, 20]
* List 3: [5, 18, 22, 30]
* <p>
* The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3.
*/
MinRangeInKSortedList minRangeInKSortedList;
@BeforeEach
public void init() {
minRangeInKSortedList = new MinRangeInKSortedList();
}
@Test
public void firstTest(){
int res= minRangeInKSortedList.findRange(
List.of(List.of(4, 10, 15, 24, 26),
List.of(0, 9, 12, 20),
List.of(5, 18, 22, 30)));
Assertions.assertEquals(res,4);
}
@Test
public void secondTest(){
int res= minRangeInKSortedList.findRange(
List.of(List.of(1,2),
List.of(2,3,4,5),
List.of(4,5,6)));
Assertions.assertEquals(res,2);
}
int findRange(List<List<Integer>> input) {
PriorityQueue<int[]> pq=new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
int[] max=new int[3];
max[0]=Integer.MIN_VALUE;
for(int i=0;i<input.size();i++){
int data=input.get(i).get(0);
if(data>max[0]){
max=new int[]{data,i,0}; // data, list, position
}
pq.add(new int[]{data,i,0});
}
int minRange=Integer.MAX_VALUE;
while (!pq.isEmpty()){
int[] min=pq.poll();
minRange=Math.min(minRange,max[0]-min[0]);
int listLoc=min[1];
int pos=min[2];
if(pos+1>=input.get(listLoc).size()) break;
int num=input.get(listLoc).get(pos+1);
if(num>max[0]){
max[0]=input.get(listLoc).get(pos+1);
max[1]=listLoc;
max[2]=pos+1;
}
pq.add(new int[]{input.get(listLoc).get(pos+1),listLoc,pos+1});
}
return minRange;
}
}
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];
}
}
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;
}
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.
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.
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
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.
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.
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.
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.
- aasshishh April 01, 2013In 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.