I tried running the code in Approach #3 (after changing the 2D array to a list of lists) but I get a "Time Limit Exceeded".
public int[] smallestRange(List<List<Integer>> nums) {
int minx = 0, miny = Integer.MAX_VALUE;
int[] next = new int[nums.size()];
boolean flag = true;
for (int i = 0; i < nums.size() && flag; i++) {
for (int j = 0; j < nums.get(i).size() && flag; j++) {
int min_i = 0, max_i = 0;
for (int k = 0; k < nums.size(); k++) {
if (nums.get(min_i).get(next[min_i]) > nums.get(k).get(next[k]))
min_i = k;
if (nums.get(max_i).get(next[max_i]) < nums.get(k).get(next[k]))
max_i = k;
}
if (miny - minx > nums.get(max_i).get(next[max_i]) - nums.get(min_i).get(next[min_i])) {
miny = nums.get(max_i).get(next[max_i]);
minx = nums.get(min_i).get(next[min_i]);
}
next[min_i]++;
if (next[min_i] == nums.get(min_i).size()) {
flag = false;
}
}
}
return new int[] {minx, miny};
}
I wonder can I do the big loop like below, when you exhaust all the nums is a speical way to special one list. The parameter changed, I haven't try this.
while (true) {
int min_i = min_queue.poll();
if (miny - minx > max - nums[min_i][next[min_i]]) {
minx = nums[min_i][next[min_i]];
miny = max;
}
next[min_i]++;
if (next[min_i] == nums[min_i].length) {
break;
}
min_queue.offer(min_i);
max = Math.max(max, nums[min_i][next[min_i]]);
}@MoriatyC
I agree that both the nested loops in Approach#3 can be replaced with a single while loop you mentioned.
@vinod23
The Approach#3 fails if any of the lists is empty.
What is the use of second for loop in the third approach (The one having the index j) ? Is it necessary ?
Very nice explanation, thanks!
I also found a different O(n log m) solution: merge all lists first and then in one pass of the merged array find the shortest subarray that contains at least one item from each list. This is very similar to the classic "find the shortest subarray that contains at least k different numbers" problem.
Accepted implementation of this approach: https://gist.github.com/andmej/49afa019be8a27a8cb7a2eecb58b7c1b