632. Smallest Range Covering Elements from K Lists

[mah-shamim]

Topics: Array, Hash Table, Greedy, Sliding Window, Sorting, Heap (Priority Queue)

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.

[kovatz]

We can use a min-heap (or priority queue) to track the smallest element from each list while maintaining a sliding window to find the smallest range that includes at least one element from each list.

Approach

1. Min-Heap Initialization: Use a min-heap to store the current elements from each of the k lists. Each heap entry will be a tuple containing the value, the index of the list it comes from, and the index of the element in that list.
2. Max Value Tracking: Keep track of the maximum value in the current window. This is important because the range is determined by the difference between the smallest element (from the heap) and the current maximum.
3. Iterate Until End of Lists: For each iteration:
   • Extract the minimum element from the heap.
   • Update the range if the current range [min_value, max_value] is smaller than the previously recorded smallest range.
   • Move to the next element in the list from which the minimum element was taken. Update the max value and add the new element to the heap.
4. Termination: The process ends when any list is exhausted.

Let's implement this solution in PHP: 632. Smallest Range Covering Elements from K Lists

<?php
/**
 * @param Integer[][] $nums
 * @return Integer[]
 */
function smallestRange($nums) {
    // Initialize a min-heap to store (value, row_index, col_index)
    $minHeap = new SplMinHeap();
    $maxValue = PHP_INT_MIN; // Keep track of the maximum value in the current window
    
    // Initialize the heap with the first element of each list
    foreach ($nums as $rowIndex => $list) {
        $minHeap->insert([$list[0], $rowIndex, 0]);
        $maxValue = max($maxValue, $list[0]);
    }
    
    // Initialize the range with the max possible values
    $rangeStart = PHP_INT_MIN;
    $rangeEnd = PHP_INT_MAX;

    // Process the heap until we can no longer include all lists in the window
    while (!$minHeap->isEmpty()) {
        list($minValue, $rowIndex, $colIndex) = $minHeap->extract();
        
        // Update the smallest range
        if ($maxValue - $minValue < $rangeEnd - $rangeStart) {
            $rangeStart = $minValue;
            $rangeEnd = $maxValue;
        }
        
        // Move to the next element in the same list (if it exists)
        if ($colIndex + 1 < count($nums[$rowIndex])) {
            $nextValue = $nums[$rowIndex][$colIndex + 1];
            $minHeap->insert([$nextValue, $rowIndex, $colIndex + 1]);
            $maxValue = max($maxValue, $nextValue);
        } else {
            // If any list is exhausted, break the loop
            break;
        }
    }
    
    return [$rangeStart, $rangeEnd];
}

// Example usage:
$nums = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]];
$result = smallestRange($nums);
print_r($result); // Output: [20, 24]
?>

Explanation:

1. Heap Initialization:
   • The initial heap contains the first element from each list. We also keep track of the maximum element among the first elements.
2. Processing the Heap:
   • Extract the minimum element from the heap, and then try to extend the range by adding the next element from the same list (if available).
   • After adding a new element to the heap, update the maxValue if the new element is larger.
   • Update the smallest range whenever the difference between the maxValue and minValue is smaller than the previously recorded range.
3. Termination:
   • The loop stops when any list runs out of elements, as we cannot include all lists in the range anymore.

Complexity Analysis

• Time Complexity: O(n * log k), where n is the total number of elements across all lists, and k is the number of lists. The complexity comes from inserting and removing elements from the heap.
• Space Complexity: O(k) for storing elements in the heap.

This solution efficiently finds the smallest range that includes at least one number from each of the k sorted lists.

[mah-shamim]

Thanks to solve the Smallest Range Covering Elements from K Lists problem

[kovatz]

Thanks