Smallest Range Covering Elements from K Lists

Problem Description

Ah, the classic “Smallest Range Covering Elements from K Lists” problem! Imagine you’re at a buffet, and you want to grab a plate that covers all your favorite dishes without having to make multiple trips. You want the smallest plate that can fit everything you love. But wait! You have K different tables, each with a different selection of food. Your mission, should you choose to accept it, is to find the smallest range that includes at least one item from each table. Sounds easy, right? Well, it’s not as simple as it sounds!

In the world of coding, this translates to finding the smallest range that covers at least one number from each of K sorted lists. So, if you’re ready to dive into the world of ranges and lists, let’s get to the code!

Code Solution


class Solution {
  public int[] smallestRange(List> nums) {
    record T(int i, int j, int num) {} // num := nums[i][j]
    Queue minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a.num, b.num));
    int mn = Integer.MAX_VALUE;
    int mx = Integer.MIN_VALUE;

    for (int i = 0; i < nums.size(); ++i) {
      final int num = nums.get(i).get(0);
      minHeap.offer(new T(i, 0, num));
      mn = Math.min(mn, num);
      mx = Math.max(mx, num);
    }

    int minRange = mn;
    int maxRange = mx;

    while (minHeap.size() == nums.size()) {
      final int i = minHeap.peek().i;
      final int j = minHeap.poll().j;
      if (j + 1 < nums.get(i).size()) {
        minHeap.offer(new T(i, j + 1, nums.get(i).get(j + 1)));
        mx = Math.max(mx, nums.get(i).get(j + 1));
        mn = minHeap.peek().num;
      }
      if (mx - mn < maxRange - minRange) {
        minRange = mn;
        maxRange = mx;
      }
    }

    return new int[] {minRange, maxRange};
  }
}

Approach

The approach taken in the code is quite elegant. It uses a min-heap (priority queue) to keep track of the smallest elements from each list. Initially, it populates the heap with the first element of each list, while also keeping track of the minimum and maximum values. The algorithm then repeatedly extracts the smallest element from the heap and checks if there are more elements in the corresponding list. If so, it adds the next element to the heap and updates the minimum and maximum values accordingly. The goal is to minimize the range (max - min) while ensuring that all lists are represented.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N log K)
Space Complexity	O(K)

Real-World Example

Imagine you’re planning a road trip with friends, and each friend has a list of must-see attractions. You want to find the smallest range of attractions that includes at least one from each friend’s list. By applying the same logic as the code above, you can efficiently determine the best set of attractions to visit without missing out on anyone's favorites!