632 Smallest Range

632. Smallest Range

1. Question

You haveklists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of theklists.

We define the range [a,b] is smaller than range [c,d] ifb-a < d-cora < cifb-a == d-c.

Example 1:

Input: [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]

Output: [20,24]

Explanation:

List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Note:

1. The given list may contain duplicates, so ascending order means >= here.

2. 1 <=k<= 3500

3. -10^5 <=value of elements<= 10^5.

2. Implementation

(1) Two Pointers + HashMap

思路：这题可以转换成Minimum Size Substring来做，首先建立一个list存储每个数和这个数所在的list的id，然后按照数的大小对list排序。接下来的做法就和Minimum Size Substring一样，维护一个Sliding Window,当这个window包含所有list的id时，则更新start pointer,结果即可

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int n = nums.size();
        int[] map = new int[n];
        List<NumInfo> list = new ArrayList<>();
        int[] res = new int[2];

        for (int i = 0; i < n; i++) {
            for (int num : nums.get(i)) {
                list.add(new NumInfo(num, i));
            }
        }

        Collections.sort(list);

        int size = list.size();
        int diff = Integer.MAX_VALUE;
        int count = 0;

        for (int start = 0, end = 0; end < size; end++) {
            if (map[list.get(end).id] == 0) {
                ++count;
            }
            ++map[list.get(end).id];

            while (count == n) {
                int curDiff = list.get(end).num - list.get(start).num;
                if (curDiff < diff) {
                    diff = curDiff;
                    res[0] = list.get(start).num;
                    res[1] = list.get(end).num;
                }

                if (map[list.get(start).id] == 1) {
                    --count;
                }
                --map[list.get(start).id];
                ++start;
            }
        }
        return res;
    }

    class NumInfo implements Comparable<NumInfo> {
        int num, id;

        public NumInfo(int num, int id) {
            this.num = num;
            this.id = id;
        }

        public int compareTo(NumInfo that) {
            return this.num - that.num;
        }
    }
}

(2) Heap

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<Element> minHeap = new PriorityQueue<>();

        int n = nums.size();
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            minHeap.add(new Element(i, 0, nums.get(i).get(0)));
            max = Math.max(max, nums.get(i).get(0));
        }

        int range = Integer.MAX_VALUE;
        int start = -1, end = -1;

        while (minHeap.size() == n) {
            Element curNum = minHeap.remove();

            if (max - curNum.val  < range) {
                range = max - curNum.val;
                start = curNum.val;
                end = max;
            }

            if (curNum.index + 1 < nums.get(curNum.row).size()) {
                int nextNum = nums.get(curNum.row).get(curNum.index + 1);
                minHeap.add(new Element(curNum.row, curNum.index + 1, nextNum));
                max = Math.max(max, nextNum);
            }
        }
        return new int[] {start, end};
    }

    class Element implements Comparable<Element> {
        int row, index, val;

        public Element(int row, int index, int val) {
            this.row = row;
            this.index = index;
            this.val = val;
        }

        public int compareTo(Element that) {
            return this.val - that.val;
        }
    }
}

3. Time & Space Complexity

Two Pointers + HashMap: 时间复杂度O(nlogn), 空间复杂度O(nk), n为nums的size， k为每个nums的平均元素个数

Heap: 时间复杂度O(nklogn), 空间复杂度O(n)