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 ?


  • 0
    W

    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


Log in to reply
 

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