What is the time complexity of LeetCode 632. Smallest Range Covering Elements from K Lists?

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 632. Smallest Range Covering Elements from K Lists?

The Python solution on this page uses O(n) auxiliary space.

Smallest Range Covering Elements from K Lists — LeetCode 632 Python Solution

HardGreedyArrayHash TableSortingSliding WindowHeap (Priority Queue)

Problem: #632
Pattern: Sliding Window
Reading time: 4 min
Source: leetcode.com

The 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.

Example

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].

Python solution

Python

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        t = [(x, i) for i, v in enumerate(nums) for x in v]
        t.sort()
        cnt = Counter()
        ans = [-inf, inf]
        j = 0
        for i, (b, v) in enumerate(t):
            cnt[v] += 1
            while len(cnt) == len(nums):
                a = t[j][0]
                x = b - a - (ans[1] - ans[0])
                if x < 0 or (x == 0 and a < ans[0]):
                    ans = [a, b]
                w = t[j][1]
                cnt[w] -= 1
                if cnt[w] == 0:
                    cnt.pop(w)
                j += 1
        return ans

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n) auxiliary

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 632. Smallest Range Covering Elements from K Lists is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 632. Smallest Range Covering Elements from K Lists?: LeetCode 632. Smallest Range Covering Elements from K Lists is rated Hard on LeetCode.
What is the time complexity of LeetCode 632. Smallest Range Covering Elements from K Lists?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 632. Smallest Range Covering Elements from K Lists?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 632. Smallest Range Covering Elements from K Lists cover?: LeetCode 632. Smallest Range Covering Elements from K Lists is tagged Greedy, Array, Hash Table, Sorting, Sliding Window and Heap (Priority Queue) on LeetCode.