hard Smallest Range Covering Elements from K Lists

Problem Statement

You are given k lists of sorted integers. Each list is in non-decreasing order.

Find the smallest range that includes at least one number from each of these k lists. 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:

• Input: nums = [[1, 5, 8], [4, 12], [7, 8, 10]]
• Expected Output: [4, 7]
• Justification: The range [4, 7] includes 5, 4, and 7 numbers from the first, second and third list respectively.

Example 2:

• Input: nums = [[3, 6, 7], [2, 4, 8], [1, 9, 10]]
• Expected Output: [1, 3]
• Justification: The range [1, 3] includes 3, 2, and 1 numbers from the first, second and third list respectively.

Example 3:

• Input: nums = [[10, 15, 24], [20, 25, 30], [12, 18, 22]]
• Expected Output: [22, 25]
• Justification: The range [22, 25] includes 24, 25, and 22 numbers from the first, second and third list respectively.

Constraints:

• nums.length == k
• 1 <= k <= 3500
• 1 <= nums[i].length <= 50
• -10⁵ <= nums[i][j] <= 10⁵
• nums[i] is sorted in non-decreasing order.

Solution

To solve this problem, we use a min-heap to efficiently track the minimum element among the heads of the k lists. By always keeping track of the current range, we can adjust it whenever we encounter a smaller range. The goal is to maintain the smallest possible range that includes at least one number from each list.

This approach ensures we efficiently find the range by leveraging the properties of a min-heap, which allows us to quickly access and update the smallest element. This method is effective because it minimizes the number of elements we need to examine, leading to a solution that balances both time and space efficiency.

Step-by-Step Algorithm

1. Initialize a Min-Heap and Max Variable:

   • Create a min-heap to store the smallest elements from each list.
   • Initialize a variable max to track the maximum value among the current elements in the heap.

2. Add First Elements of Each List to the Heap:

   • For each list, add its first element to the min-heap along with the list index and element index.
   • Update the max variable to be the maximum value of these first elements.

3. Initialize Range Variables:

   • Initialize rangeStart and rangeEnd to track the smallest range found.

4. Process the Min-Heap:

   • While the heap contains elements from all lists (heap size equals number of lists):
     • Extract the smallest element from the heap (this gives the current minimum value).
     • Update the smallest range (rangeStart and rangeEnd) if the current range is smaller than the previously found range.
     • If the extracted element is not the last in its list, add the next element from the same list to the heap and update the max variable.

5. Return the Smallest Range:

   • After processing all elements, return the smallest range [rangeStart, rangeEnd].

Algorithm Walkthrough

Let's walk through the algorithm step-by-step using nums = [[10, 15, 24], [20, 25, 30], [12, 18, 22]]:

1. Initialize Min-Heap and Max Variable:

   • Min-Heap: []
   • Max: -Infinity

2. Add First Elements of Each List to the Heap:

   • Add 10 from list 0: Heap = [(10, 0, 0)], Max = 10
   • Add 20 from list 1: Heap = [(10, 0, 0), (20, 1, 0)], Max = 20
   • Add 12 from list 2: Heap = [(10, 0, 0), (20, 1, 0), (12, 2, 0)], Max = 20

3. Initialize Range Variables:

   • rangeStart = 0, rangeEnd = Infinity

4. Process the Min-Heap:

   • Step 1:
     • Extract 10 from the heap: Min-Heap = [(12, 2, 0), (20, 1, 0)], Current Min = 10
     • Update Range: rangeStart = 10, rangeEnd = 20
     • Add 15 from list 0: Min-Heap = [(12, 2, 0), (20, 1, 0), (15, 0, 1)], Max = 20
   • Step 2:
     • Extract 12 from the heap: Min-Heap = [(15, 0, 1), (20, 1, 0)], Current Min = 12
     • Update Range: rangeStart = 12, rangeEnd = 20
     • Add 18 from list 2: Min-Heap = [(15, 0, 1), (20, 1, 0), (18, 2, 1)], Max = 20
   • Step 3:
     • Extract 15 from the heap: Min-Heap = [(18, 2, 1), (20, 1, 0)], Current Min = 15
     • Update Range: rangeStart = 15, rangeEnd = 20
     • Add 24 from list 0: Min-Heap = [(18, 2, 1), (20, 1, 0), (24, 0, 2)], Max = 24
   • Step 4:
     • Extract 18 from the heap: Min-Heap = [(20, 1, 0), (24, 0, 2)], Current Min = 18
     • Update Range: rangeStart = 18, rangeEnd = 24
     • Add 22 from list 2: Min-Heap = [(20, 1, 0), (24, 0, 2), (22, 2, 2)], Max = 24
   • Step 5:
     • Extract 20 from the heap: Min-Heap = [(22, 2, 2), (24, 0, 2)], Current Min = 20
     • Update Range: rangeStart = 20, rangeEnd = 24
     • Add 25 from list 1: Min-Heap = [(22, 2, 2), (24, 0, 2), (25, 1, 1)], Max = 25
   • Step 6:
     • Extract 22 from the heap: Min-Heap = [(24, 0, 2), (25, 1, 1)], Current Min = 22
     • Update Range: rangeStart = 22, rangeEnd = 25
     • List 2 is exhausted, so the algorithm terminates.

5. Return the Smallest Range:

   • The smallest range is [22, 25].

Code

import java.util.*;

class Solution {

  public int[] smallestRange(List<List<Integer>> nums) {
    // Min-heap to store the smallest elements from each list
    PriorityQueue<int[]> minHeap = new PriorityQueue<>(
      Comparator.comparingInt(a -> a[0])
    );
    int max = Integer.MIN_VALUE;

    // Initialize the heap with the first element of each list and find the initial max value
    for (int i = 0; i < nums.size(); i++) {
      minHeap.offer(new int[] { nums.get(i).get(0), i, 0 });
      max = Math.max(max, nums.get(i).get(0));
    }

    // Variables to track the smallest range
    int rangeStart = 0, rangeEnd = Integer.MAX_VALUE;

    // Process the heap
    while (minHeap.size() == nums.size()) {
      int[] curr = minHeap.poll();
      int currMin = curr[0], listIndex = curr[1], elemIndex = curr[2];

      // Update the smallest range if the current range is smaller
      if (rangeEnd - rangeStart > max - currMin) {
        rangeStart = currMin;
        rangeEnd = max;
      }

      // If the list has more elements, add the next element to the heap
      if (elemIndex + 1 < nums.get(listIndex).size()) {
        int nextElem = nums.get(listIndex).get(elemIndex + 1);
        minHeap.offer(new int[] { nextElem, listIndex, elemIndex + 1 });
        max = Math.max(max, nextElem);
      }
    }

    return new int[] { rangeStart, rangeEnd };
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    List<List<Integer>> example1 = Arrays.asList(
      Arrays.asList(1, 5, 8),
      Arrays.asList(4, 12),
      Arrays.asList(7, 8, 10)
    );
    System.out.println(Arrays.toString(sol.smallestRange(example1))); // Output: [4, 7]

    List<List<Integer>> example2 = Arrays.asList(
      Arrays.asList(3, 6, 7),
      Arrays.asList(2, 4, 8),
      Arrays.asList(1, 9, 10)
    );
    System.out.println(Arrays.toString(sol.smallestRange(example2))); // Output: [1, 3]

    List<List<Integer>> example3 = Arrays.asList(
      Arrays.asList(10, 15, 24),
      Arrays.asList(20, 25, 30),
      Arrays.asList(12, 18, 22)
    );
    System.out.println(Arrays.toString(sol.smallestRange(example3))); // Output: [22, 25]
  }
}

Complexity Analysis

Time Complexity

The time complexity of this algorithm is , where (N) is the total number of elements across all lists and (K) is the number of lists.

• Initializing the min-heap takes time.
• Each insertion and extraction from the heap takes time.
• Since we process each element once, the total number of operations is (N), where (N) is the total number of elements in all lists combined.

Thus, the overall time complexity is .

Space Complexity

The space complexity is .

• The min-heap stores one element from each of the (K) lists at any given time.
• Additional space is used for variables to keep track of the maximum value and the current range.

Therefore, the space complexity is .