Smallest Range

vinod23

Click here to see the full article post

woshifumingyuan

Thank you for the solutions.
I just wonder where is the animation.

vinod23

@woshifumingyuan It's visible now. Please have a look

ro_d99

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

MoriatyC

@ro_d99 I have the same problem.

vinod23

@MoriatyC @ro_d99 Thanks for pointing it out. I have changed it to "Time Limit Exceeded".

MoriatyC

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