Smallest Range



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]]); }

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