632. Smallest Range Covering Elements from K Lists
Smallest Range Covering Elements from K Lists (LeetCode 632) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the K-way Merge subpattern.
How to solve Smallest Range Covering Elements from K Lists
Smallest Range Covering Elements from K Lists is a K-way Merge Using Heap problem, part of Heap (Priority Queue) Patterns. Master K-way merge pattern using min heap. Merge k sorted lists and find kth smallest in matrix.
Work towards the solution in these steps:
- Consider how to efficiently keep track of the smallest and largest elements among the current candidates from each list to determine potential ranges.
- Think about using a min-heap (priority queue) to always access the smallest current element across the k lists while keeping track of the maximum element among them.
- Initialize the heap with the first element of each list and record the current maximum; this will help define the initial range.
The reference solution runs in O(N log k) time and O(k) space.
The Smallest Range Covering Elements from K Lists solution and editorial walks through the full approach with reference code.
Problem statement
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.
Example 1:
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:
Input: nums = [[1,2,3],[1,2,3],[1,2,3]] Output: [1,1]
Constraints:
- nums.length == k
- 1 <= k <= 3500
- 1 <= nums[i].length <= 50
- -105 <= nums[i][j] <= 105
- nums[i] is sorted in non-decreasing order.
Topics and companies
Topics: Array, Hash Table, Greedy, Sliding Window, Sorting, Heap (Priority Queue).
Reported in interviews at Amazon.
How to practise Smallest Range Covering Elements from K Lists on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N log k) time and O(k) space.
Open Smallest Range Covering Elements from K Lists in the code editor, or read the Smallest Range Covering Elements from K Lists editorial for a worked solution with its approach and complexity analysis.
Where Smallest Range Covering Elements from K Lists sits in the DSA pattern sheet
Problems related to Smallest Range Covering Elements from K Lists
Other problems that use the same K-way Merge and Heap (Priority Queue) Patterns techniques:
- Design Twitter — Medium, same subpattern
- Find K Pairs with Smallest Sums — Medium, same subpattern
- Kth Smallest Element in a Sorted Matrix — Medium, same subpattern
- Merge k Sorted Lists — Hard, same subpattern
- Finding MK Average — Hard, same pattern
- Find Median from Data Stream — Hard, same pattern
Smallest Range Covering Elements from K Lists FAQ
What is the LeetCode number of Smallest Range Covering Elements from K Lists?
Smallest Range Covering Elements from K Lists is LeetCode problem 632, rated Hard.
What pattern is used to solve Smallest Range Covering Elements from K Lists?
Smallest Range Covering Elements from K Lists is a K-way Merge Using Heap problem. It belongs to the Heap (Priority Queue) Patterns pattern, in the K-way Merge subpattern.
What is the time complexity of Smallest Range Covering Elements from K Lists?
The reference solution runs in O(N log k) time and O(k) space.
Which companies ask Smallest Range Covering Elements from K Lists?
Smallest Range Covering Elements from K Lists has been reported in interviews at Amazon.