> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/priority-queue/smallest-range-covering-elements-from-k-lists.md).

# Smallest Range Covering Elements from K Lists

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. -105 <= `value of elements` <= 105.

```java
class Solution {
    static class pair {
        int value, row, index;

        pair(int value, int row, int index) {
            this.value = value;
            this.row = row;
            this.index = index;
        }
    }

    public int[] smallestRange(List<List<Integer>> nums) {
        if (nums.size() == 1) {
            return new int[] { nums.get(0).get(0), nums.get(0).get(0) };
        }
        int upperBound = Integer.MIN_VALUE;
        PriorityQueue<pair> pq = new PriorityQueue<>((a, b) -> a.value - b.value);
        for (int i = 0; i < nums.size(); i++) {
            pq.add(new pair(nums.get(i).get(0), i, 0));
            upperBound = Math.max(upperBound, nums.get(i).get(0));
        }
        int range = Integer.MAX_VALUE;
        int minRange = -1, maxRange = -1;
        while (pq.size() == nums.size()) {
            int lowerBound = pq.peek().value;
            if (range > upperBound - lowerBound) {
                range = upperBound - lowerBound;
                minRange = lowerBound;
                maxRange = upperBound;
            }
            pair pop = pq.poll();
            if (pop.index >= nums.get(pop.row).size() - 1)
                break;
            pq.add(new pair(nums.get(pop.row).get(pop.index + 1), pop.row, pop.index + 1));
            upperBound = Math.max(upperBound, nums.get(pop.row).get(pop.index + 1));
        }
        int[] ans = new int[] { minRange, maxRange };
        return ans;
    }
}
```