Smallest Range


  • 0

    Click here to see the full article post


  • 0
    W

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


  • 0

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


  • 0
    R

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

  • 0
    M

    @ro_d99 I have the same problem.


  • 0

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


  • 0
    M

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

  • 0
    N

    @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.


  • 0
    B

    What is the use of second for loop in the third approach (The one having the index j) ? Is it necessary ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.