# 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)**


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/algorithm-practice/leetcode/two-pointers/632-smallest-range.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.