Java Two Solutions, PriorityQueue and Sliding Window


  • 0

    Method 1:
    first put the smallest element of each list into the priorityqueue
    poll the smallest one and add it's successor in its own list into priorityqueue so we can potentially increase the lower bound and reduce the window length.
    keep doing this till we run out of elements for one of the list.

       public int[] smallestRange(List<List<Integer>> nums) {
            PriorityQueue<int[]> minheap = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] - o2[0];
                }
            });
            int k = nums.size(), len = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
            int[] ans = null;
            for (int i = 0; i < k; i++) {
                int n = nums.get(i).get(0);
                max = Math.max(max, n);
                minheap.add(new int[]{n, 0, i});
            }
            while (minheap.size() == k) {
                int[] min = minheap.poll();
                if (len > max-min[0]+1) {
                    len = max-min[0]+1;
                    ans = new int[]{min[0], max};
                }
                if (min[1] < nums.get(min[2]).size()-1) {
                    int n = nums.get(min[2]).get(min[1]+1);
                    max = Math.max(max, n);
                    minheap.add(new int[]{n, min[1]+1, min[2]});
                }
            }
            return ans;
        }
    

    Method 2:
    combine all the elements into a single list and discard duplicates from the same list, this is nlogk if we use a minheap.
    using sliding window similar to 76. Minimum Window Substring to get the smallest window.

        public int[] smallestRange(List<List<Integer>> nums) {
            ArrayList<int[]> list = new ArrayList<>();
            int k = nums.size(), len = Integer.MAX_VALUE;
            PriorityQueue<int[]> minheap = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] - o2[0];
                }
            });
            for (int i = 0; i < k; i++) {
                minheap.add(new int[]{nums.get(i).get(0), 0, i});
            }
            while (!minheap.isEmpty()) {
                int[] min = minheap.poll();
                list.add(min);
                int i = min[1]+1;
                List<Integer> l = nums.get(min[2]);
                while (i < l.size() && l.get(i) == l.get(min[1])) i++;
                if (i < l.size()) minheap.add(new int[]{l.get(i), i, min[2]});
            }
            int[] count = new int[k], ans = null;
            for (int i = 0, j = 0, n = 0; i < list.size(); i++) {
                int[] a = list.get(i);
                if (count[a[2]]++ == 0 && ++n == k) {
                    while (--count[list.get(j++)[2]] > 0);
                    n--;
                    if (len > a[0]-list.get(j-1)[0]+1) {
                        len = a[0]-list.get(j-1)[0]+1;
                        ans = new int[]{list.get(j-1)[0], list.get(i)[0]};
                    }
                }
            }
            return ans;
        }
    

Log in to reply
 

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