# 632 Smallest Range

## 632. [Smallest Range](https://leetcode.com/problems/smallest-range/description/)

## 1. Question

You have`k`lists of sorted integers in ascending order. Find the **smallest** range that includes at least one number from each of the`k`lists.

We define the range \[a,b] is smaller than range \[c,d] if`b-a < d-c`or`a < c`if`b-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,结果即可

```java
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**

```java
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)**