Smallest Range Covering Elements from K Lists

Problem

You have k lists of sorted integers in non-decreasing 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.

Examples

Example 1

1
2
3
4
5
6


Input: nums = [[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].

Example 2

1
2


Input: nums = [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]

Solution

Method 1 - Naive Approach

Intuition

The brute-force idea is to keep a pointer for each list and always consider the current elements pointed to by these pointers. At each step, we look for the minimum and maximum among these elements, and update the smallest range if the current range is smaller. We then move the pointer of the list that contains the minimum element forward. This ensures that every range considered always contains at least one element from each list.

Approach

Initialize an array of pointers, one for each list, all starting at index 0.
Repeat the following until any pointer reaches the end of its list:
- Collect the current elements from each list using the pointers.
- Find the minimum and maximum among these elements.
- If the current range (max - min) is smaller than the best found so far, update the result.
- Move forward the pointer of the list that contains the minimum element.
When any list is exhausted, stop and return the smallest range found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int k = nums.size();
        vector<int> ptr(k, 0);
        int minRange = INT_MAX, minStart = 0, minEnd = 0;
        while (true) {
            int minVal = INT_MAX, maxVal = INT_MIN, minIdx = -1;
            for (int i = 0; i < k; ++i) {
                if (ptr[i] == nums[i].size()) return {minStart, minEnd};
                int val = nums[i][ptr[i]];
                if (val < minVal) {
                    minVal = val;
                    minIdx = i;
                }
                if (val > maxVal) maxVal = val;
            }
            if (maxVal - minVal < minRange) {
                minRange = maxVal - minVal;
                minStart = minVal;
                minEnd = maxVal;
            }
            ptr[minIdx]++;
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


func smallestRange(nums [][]int) []int {
    k := len(nums)
    ptr := make([]int, k)
    minRange, minStart, minEnd := 1<<31-1, 0, 0
    for {
        minVal, maxVal, minIdx := 1<<31-1, -1<<31, -1
        for i := 0; i < k; i++ {
            if ptr[i] == len(nums[i]) {
                return []int{minStart, minEnd}
            }
            val := nums[i][ptr[i]]
            if val < minVal {
                minVal = val
                minIdx = i
            }
            if val > maxVal {
                maxVal = val
            }
        }
        if maxVal-minVal < minRange {
            minRange = maxVal - minVal
            minStart = minVal
            minEnd = maxVal
        }
        ptr[minIdx]++
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int k = nums.size();
        int[] ptr = new int[k];
        int minRange = Integer.MAX_VALUE, minStart = 0, minEnd = 0;
        while (true) {
            int minVal = Integer.MAX_VALUE, maxVal = Integer.MIN_VALUE, minIdx = -1;
            for (int i = 0; i < k; i++) {
                if (ptr[i] == nums.get(i).size()) return new int[]{minStart, minEnd};
                int val = nums.get(i).get(ptr[i]);
                if (val < minVal) {
                    minVal = val;
                    minIdx = i;
                }
                if (val > maxVal) maxVal = val;
            }
            if (maxVal - minVal < minRange) {
                minRange = maxVal - minVal;
                minStart = minVal;
                minEnd = maxVal;
            }
            ptr[minIdx]++;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution {
    fun smallestRange(nums: List<List<Int>>): IntArray {
        val k = nums.size
        val ptr = IntArray(k)
        var minRange = Int.MAX_VALUE
        var minStart = 0
        var minEnd = 0
        while (true) {
            var minVal = Int.MAX_VALUE
            var maxVal = Int.MIN_VALUE
            var minIdx = -1
            for (i in 0 until k) {
                if (ptr[i] == nums[i].size) return intArrayOf(minStart, minEnd)
                val v = nums[i][ptr[i]]
                if (v < minVal) {
                    minVal = v
                    minIdx = i
                }
                if (v > maxVal) maxVal = v
            }
            if (maxVal - minVal < minRange) {
                minRange = maxVal - minVal
                minStart = minVal
                minEnd = maxVal
            }
            ptr[minIdx]++
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution:
    def smallestRange(self, nums: list[list[int]]) -> list[int]:
        k = len(nums)
        ptr = [0] * k
        min_range = float('inf')
        min_start = min_end = 0
        while True:
            min_val = float('inf')
            max_val = float('-inf')
            min_idx = -1
            for i in range(k):
                if ptr[i] == len(nums[i]):
                    return [min_start, min_end]
                v = nums[i][ptr[i]]
                if v < min_val:
                    min_val = v
                    min_idx = i
                if v > max_val:
                    max_val = v
            if max_val - min_val < min_range:
                min_range = max_val - min_val
                min_start = min_val
                min_end = max_val
            ptr[min_idx] += 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


impl Solution {
    pub fn smallest_range(nums: Vec<Vec<i32>>) -> Vec<i32> {
        let k = nums.len();
        let mut ptr = vec![0; k];
        let mut min_range = i32::MAX;
        let (mut min_start, mut min_end) = (0, 0);
        loop {
            let mut min_val = i32::MAX;
            let mut max_val = i32::MIN;
            let mut min_idx = 0;
            for i in 0..k {
                if ptr[i] == nums[i].len() {
                    return vec![min_start, min_end];
                }
                let v = nums[i][ptr[i]];
                if v < min_val {
                    min_val = v;
                    min_idx = i;
                }
                if v > max_val {
                    max_val = v;
                }
            }
            if max_val - min_val < min_range {
                min_range = max_val - min_val;
                min_start = min_val;
                min_end = max_val;
            }
            ptr[min_idx] += 1;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
    smallestRange(nums: number[][]): number[] {
        const k = nums.length;
        const ptr = new Array(k).fill(0);
        let minRange = Number.MAX_SAFE_INTEGER, minStart = 0, minEnd = 0;
        while (true) {
            let minVal = Number.MAX_SAFE_INTEGER, maxVal = Number.MIN_SAFE_INTEGER, minIdx = -1;
            for (let i = 0; i < k; ++i) {
                if (ptr[i] === nums[i].length) return [minStart, minEnd];
                const v = nums[i][ptr[i]];
                if (v < minVal) {
                    minVal = v;
                    minIdx = i;
                }
                if (v > maxVal) maxVal = v;
            }
            if (maxVal - minVal < minRange) {
                minRange = maxVal - minVal;
                minStart = minVal;
                minEnd = maxVal;
            }
            ptr[minIdx]++;
        }
    }
}

Complexity

⏰ Time complexity: O(n * k), where n is the length of the longest list and k is the number of lists. For each step, we scan all k lists to find min and max.
🧺 Space complexity: O(k), for the pointers array.

Method 2 - Min-Heap (Priority Queue)

Intuition

To efficiently find the smallest range covering at least one element from each list, we use a min-heap to always access the current minimum among the chosen elements, while tracking the current maximum. By always advancing the pointer in the list that contributed the minimum, we ensure all ranges considered are valid and can update the best range found.

Approach

Initialize a min-heap (priority queue) that stores tuples of (value, list index, element index).
Insert the first element from each list into the heap and track the current maximum value among them.
While the heap contains one element from each list:
- Pop the minimum element from the heap.
- If the current range (max - min) is smaller than the best found, update the result.
- If the list of the popped element has more elements, push the next element from that list into the heap and update the current maximum if needed.
- If any list is exhausted, stop.
Return the smallest range found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


#include <queue>
class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        using T = tuple<int, int, int>; // value, row, idx
        auto cmp = [](const T& a, const T& b) { return get<0>(a) > get<0>(b); };
        priority_queue<T, vector<T>, decltype(cmp)> minHeap(cmp);
        int maxVal = INT_MIN;
        for (int i = 0; i < nums.size(); ++i) {
            minHeap.emplace(nums[i][0], i, 0);
            maxVal = max(maxVal, nums[i][0]);
        }
        int rangeStart = 0, rangeEnd = INT_MAX;
        while (minHeap.size() == nums.size()) {
            auto [val, row, idx] = minHeap.top(); minHeap.pop();
            if (maxVal - val < rangeEnd - rangeStart) {
                rangeStart = val;
                rangeEnd = maxVal;
            }
            if (idx + 1 < nums[row].size()) {
                int nextVal = nums[row][idx + 1];
                minHeap.emplace(nextVal, row, idx + 1);
                maxVal = max(maxVal, nextVal);
            }
        }
        return {rangeStart, rangeEnd};
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


import "container/heap"
type Element struct{ val, row, idx int }
type MinHeap []Element
func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].val < h[j].val }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Element)) }
func (h *MinHeap) Pop() interface{}   { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }

func smallestRange(nums [][]int) []int {
    k := len(nums)
    h := &MinHeap{}
    maxVal := -1 << 31
    for i := 0; i < k; i++ {
        heap.Push(h, Element{nums[i][0], i, 0})
        if nums[i][0] > maxVal { maxVal = nums[i][0] }
    }
    rangeStart, rangeEnd := 0, 1<<31-1
    for h.Len() == k {
        e := heap.Pop(h).(Element)
        if maxVal-e.val < rangeEnd-rangeStart {
            rangeStart, rangeEnd = e.val, maxVal
        }
        if e.idx+1 < len(nums[e.row]) {
            nextVal := nums[e.row][e.idx+1]
            heap.Push(h, Element{nextVal, e.row, e.idx + 1})
            if nextVal > maxVal { maxVal = nextVal }
        }
    }
    return []int{rangeStart, rangeEnd}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int maxVal = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size(); i++) {
            int v = nums.get(i).get(0);
            minHeap.offer(new int[]{v, i, 0});
            maxVal = Math.max(maxVal, v);
        }
        int rangeStart = 0, rangeEnd = Integer.MAX_VALUE;
        while (minHeap.size() == nums.size()) {
            int[] curr = minHeap.poll();
            int val = curr[0], row = curr[1], idx = curr[2];
            if (maxVal - val < rangeEnd - rangeStart) {
                rangeStart = val;
                rangeEnd = maxVal;
            }
            if (idx + 1 < nums.get(row).size()) {
                int nextVal = nums.get(row).get(idx + 1);
                minHeap.offer(new int[]{nextVal, row, idx + 1});
                maxVal = Math.max(maxVal, nextVal);
            }
        }
        return new int[]{rangeStart, rangeEnd};
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


import java.util.PriorityQueue
class Solution {
    fun smallestRange(nums: List<List<Int>>): IntArray {
        val minHeap = PriorityQueue(compareBy<Pair<Int, Pair<Int, Int>>> { it.first })
        var maxVal = Int.MIN_VALUE
        for (i in nums.indices) {
            val v = nums[i][0]
            minHeap.offer(Pair(v, Pair(i, 0)))
            maxVal = maxOf(maxVal, v)
        }
        var rangeStart = 0
        var rangeEnd = Int.MAX_VALUE
        while (minHeap.size == nums.size) {
            val (valMin, pair) = minHeap.poll()
            val (row, idx) = pair
            if (maxVal - valMin < rangeEnd - rangeStart) {
                rangeStart = valMin
                rangeEnd = maxVal
            }
            if (idx + 1 < nums[row].size) {
                val nextVal = nums[row][idx + 1]
                minHeap.offer(Pair(nextVal, Pair(row, idx + 1)))
                maxVal = maxOf(maxVal, nextVal)
            }
        }
        return intArrayOf(rangeStart, rangeEnd)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


import heapq
class Solution:
    def smallestRange(self, nums: list[list[int]]) -> list[int]:
        heap = []
        max_val = float('-inf')
        for row, arr in enumerate(nums):
            heapq.heappush(heap, (arr[0], row, 0))
            max_val = max(max_val, arr[0])
        range_start, range_end = 0, float('inf')
        k = len(nums)
        while len(heap) == k:
            val, row, idx = heapq.heappop(heap)
            if max_val - val < range_end - range_start:
                range_start, range_end = val, max_val
            if idx + 1 < len(nums[row]):
                next_val = nums[row][idx + 1]
                heapq.heappush(heap, (next_val, row, idx + 1))
                max_val = max(max_val, next_val)
        return [range_start, range_end]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
    pub fn smallest_range(nums: Vec<Vec<i32>>) -> Vec<i32> {
        let k = nums.len();
        let mut heap = BinaryHeap::new();
        let mut max_val = i32::MIN;
        for (row, arr) in nums.iter().enumerate() {
            heap.push(Reverse((arr[0], row, 0)));
            max_val = max_val.max(arr[0]);
        }
        let mut range_start = 0;
        let mut range_end = i32::MAX;
        while heap.len() == k {
            let Reverse((val, row, idx)) = heap.pop().unwrap();
            if max_val - val < range_end - range_start {
                range_start = val;
                range_end = max_val;
            }
            if idx + 1 < nums[row].len() {
                let next_val = nums[row][idx + 1];
                heap.push(Reverse((next_val, row, idx + 1)));
                max_val = max_val.max(next_val);
            }
        }
        vec![range_start, range_end]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


class MinHeap {
    private data: [number, number, number][] = [];
    push(item: [number, number, number]) {
        this.data.push(item);
        this.data.sort((a, b) => a[0] - b[0]);
    }
    pop(): [number, number, number] | undefined {
        return this.data.shift();
    }
    get size() { return this.data.length; }
}
class Solution {
    smallestRange(nums: number[][]): number[] {
        const k = nums.length;
        const heap = new MinHeap();
        let maxVal = -Infinity;
        for (let i = 0; i < k; i++) {
            heap.push([nums[i][0], i, 0]);
            maxVal = Math.max(maxVal, nums[i][0]);
        }
        let rangeStart = 0, rangeEnd = Infinity;
        while (heap.size === k) {
            const [val, row, idx] = heap.pop()!;
            if (maxVal - val < rangeEnd - rangeStart) {
                rangeStart = val;
                rangeEnd = maxVal;
            }
            if (idx + 1 < nums[row].length) {
                const nextVal = nums[row][idx + 1];
                heap.push([nextVal, row, idx + 1]);
                maxVal = Math.max(maxVal, nextVal);
            }
        }
        return [rangeStart, rangeEnd];
    }
}

Complexity

⏰ Time complexity: O(n log k), where n is the total number of elements and k is the number of lists. Each heap operation is O(log k) and we process each element once.
🧺 Space complexity: O(k), for the heap storing one element from each list.

Problem#

Examples#

Example 1#

Example 2#

Solution#

Method 1 - Naive Approach#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Min-Heap (Priority Queue)#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Example 1

Example 2

Solution

Method 1 - Naive Approach

Intuition

Approach

Code

Complexity

Method 2 - Min-Heap (Priority Queue)

Intuition

Approach

Code

Complexity