Smallest Range Covering Elements from K Lists

Clarify the problem

  • The problem is to find the smallest range that contains at least one element from each of the K lists.
  • Each list is sorted in ascending order.
  • The range is defined as the difference between the maximum and minimum values in the range.

Analyze the problem

  • Input: K sorted lists, where K is the number of lists.
  • Output: Return the smallest range that covers at least one element from each list.
  • Constraints: The number of elements in each list can be up to 5 * 10^4.

Design an algorithm

  • Initialize a priority queue to store the current minimum and maximum values along with the list and index they belong to.
  • Initialize the priority queue with the first element from each list.
  • Initialize variables to keep track of the current range.
  • While the priority queue is not empty:
    • Pop the element with the smallest value from the priority queue.
    • Update the range if the current range is smaller.
    • If the popped element's list has more elements, add the next element from that list to the priority queue.
  • Return the smallest range found.

Explain your approach

  • By using a priority queue, we can efficiently keep track of the minimum and maximum values while exploring the elements from the K lists.
  • We start with the first element from each list and keep adding the next element from the list with the smallest value.
  • By doing so, we maintain a sliding window that covers at least one element from each list.
  • We update the range whenever a smaller range is found.

 

Write clean and readable code

class Element:
    def __init__(self, value, list_idx, idx):
        self.value = value
        self.list_idx = list_idx
        self.idx = idx

    def __lt__(self, other):
        return self.value < other.value


def smallestRange(nums):
    pq = []
    maximum = float('-inf')
    for i, lst in enumerate(nums):
        pq.append(Element(lst[0], i, 0))
        maximum = max(maximum, lst[0])

    heapq.heapify(pq)
    smallest_range = (float('-inf'), float('inf'))

    while len(pq) == len(nums):
        smallest = heapq.heappop(pq)
        if maximum - smallest.value < smallest_range[1] - smallest_range[0]:
            smallest_range = (smallest.value, maximum)

        if smallest.idx + 1 < len(nums[smallest.list_idx]):
            next_element = Element(nums[smallest.list_idx][smallest.idx + 1], smallest.list_idx, smallest.idx + 1)
            heapq.heappush(pq, next_element)
            maximum = max(maximum, next_element.value)

    return smallest_range

Test your code


nums = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]
print(smallestRange(nums))
Expected output: (20, 24)

nums = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(smallestRange(nums))
Expected output: (1, 7)

nums = [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15]]
print(smallestRange(nums))
Expected output: (1, 11)

Optimize if necessary

  • The provided solution already uses an efficient approach using a priority queue to track the minimum and maximum values.
  • There is no further optimization required.

Handle error cases

  • If the input nums is empty or contains no lists, return None as there is no range to be found.

Discuss complexity analysis

  • The time complexity of the solution is O(N log K), where N is the total number of elements in all lists and K is the number of lists.
  • The space complexity is O(K) for the priority queue, as we store at most K elements.
  • The solution is efficient and scalable even for large input sizes.

 

Next Post Previous Post