How to Solve Smallest Range Covering Elements from K Lists

Start by flattening all list elements into a value-index pair and sort them. Use a sliding window with a hash map to track coverage of all k lists. Expand the window until all lists are represented, then shrink from the left to maintain the minimal range, updating whenever a smaller valid range is found.

Problem Statement

You are given k lists of integers, each sorted in non-decreasing order. Your task is to identify the smallest continuous range [a, b] such that at least one number from each list falls within this range. The range is considered smaller if its length is shorter, or if lengths are equal, the range starting earlier is preferred.

Implement a function that accepts an array of k sorted lists and returns the smallest range covering all lists. Example: given nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]], the output should be [20,24] because each list contributes at least one number within this interval.

Examples

Example 1

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]

Output: [20,24]

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]

Example details omitted.

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.

Solution Approach

Flatten and sort all numbers

Convert each list element into a tuple of (value, list_index) and combine all lists into a single array. Sort this array by value to allow sequential scanning while maintaining knowledge of which list each number belongs to.

Use sliding window with hash map

Maintain a window over the sorted array and track the count of elements from each list using a hash map. Expand the window to include at least one number from every list, then attempt to shrink from the left to minimize the range while preserving coverage.

Update minimal range efficiently

Whenever the window contains all k lists, compare the current window's range with the recorded minimal range. Replace the minimal range if the current window is smaller or starts earlier with the same length. Continue until the end of the array is reached.

Complexity Analysis

Flattening and sorting takes O(n log n) where n is the total number of elements. Sliding window passes over each element once, and hash map operations are O(1) average, leading to O(n) additional time. Space is O(n) for storing the flattened array and hash counts.

What Interviewers Usually Probe

• Pay attention to maintaining a valid window covering all lists as early as possible.
• Hash map usage shows understanding of list indexing and coverage tracking.
• Efficiency concerns arise if you attempt nested loops over lists rather than flattening and scanning.

Common Pitfalls or Variants

Common pitfalls

• Assuming numbers are uniformly distributed and skipping window shrink checks, causing suboptimal range selection.
• Ignoring duplicate numbers across lists, which may miscount coverage in the hash map.
• Overcomplicating with separate priority queues per list instead of one global sorted structure.

Follow-up variants

• Return all ranges that tie for minimal length instead of just the first found.
• Allow unsorted input lists, requiring initial sorting of each list before flattening.
• Compute smallest range with exactly one number from each list, enforcing single selection per list.

How GhostInterview Helps

• Automatically generates the flattened array and tracks coverage to minimize window range.
• Highlights optimal window expansions and shrink operations, preventing typical off-by-one errors.
• Provides clear, incremental updates of minimal range with debugging hints tied to the exact pattern.

Topic Pages

• Array
• Hash Table
• Greedy
• Sliding Window
• Sorting
• Heap (Priority Queue)

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the best approach for Smallest Range Covering Elements from K Lists?

Flatten all numbers with their source list indices, sort them, then use a sliding window with a hash map to track coverage and find the minimal range.

Can this problem be solved without sorting?

Sorting is essential for efficient scanning; without it, you risk O(n^2) checks and missing minimal range opportunities.

How do you handle duplicate numbers across different lists?

Include duplicates in the flattened array but ensure the hash map counts the number of lists covered, not individual duplicates, to maintain correct coverage.

What are common mistakes in the array scanning plus hash lookup approach?

Failing to shrink the window correctly, miscounting covered lists, or forgetting to update the minimal range whenever a valid window is found.

Does the problem pattern favor greedy or heap strategies?

The primary pattern is array scanning plus hash lookup. A heap can help in alternative implementations, but the most direct method uses sorted array and sliding window for minimal range.