Slide window solution without PriorityQueue


  • 0
    T

    This is the same idea as https://discuss.leetcode.com/topic/87884/8-lines-slide-window-solution-in-java

        public int[] smallestRange(List<List<Integer>> nums) {
            int k = nums.size();
            List<int[]> list= new ArrayList<>();
            for(int i = 0; i < k; i++) {
                for(int x : nums.get(i)) {
                    list.add(new int[]{x, i});
                }
            }
            Collections.sort(list, (a,b) -> (a[0] - b[0]));
            int min = -1, max = 2000000, count = 0, pre = 0;
            int[] flag = new int[k];
            for(int i = 0; i < list.size(); i++) {
                int[] e = list.get(i);
                if (flag[e[1]]++ == 0) {
                    count++;
                    while(count == k) {
                        if (e[0] - list.get(pre)[0] < max - min) {
                            min = list.get(pre)[0];
                            max = e[0];
                        }
                        if (--flag[list.get(pre++)[1]] == 0) count--;
                    }
                }
            }
            
            return new int[] {min, max};
        }
    

Log in to reply
 

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