• Posts

Problem 632 Smallest Range Covering Elements from K Lists

Problem Statement

Link - Problem 632

Question

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.

Solution

typedef pair<int,pair<int,int>> pr;

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        // Priority queue to store (value, list index, element index)
        priority_queue<pr,vector<pr>,greater<>>pq;
        int maxVal = INT_MIN, rangeStart = 0, rangeEnd = INT_MAX;

        // Insert the first element from each list into the min-heap
        for (int i = 0; i < nums.size(); i++) {
            pq.push({nums[i][0], {i, 0}});
            maxVal = max(maxVal, nums[i][0]);
        }

        // Continue until we can't proceed further
        while (pq.size() == nums.size()) {
            auto [minVal, indices] = pq.top();
            pq.pop();
            int row = indices.first, col = indices.second;

            // Update the smallest range
            if (maxVal - minVal < rangeEnd - rangeStart) {
                rangeStart = minVal;
                rangeEnd = maxVal;
            }

            // If possible, add the next element from the same row to the heap
            if (col + 1 < nums[row].size()) {
                int nextVal = nums[row][col + 1];
                pq.push({nextVal, {row, col + 1}});
                maxVal = max(maxVal, nextVal);
            }
        }

        return {rangeStart, rangeEnd};
    }
};

Complexity Analysis

| Algorithm                     | Time Complexity | Space Complexity |
| ----------------------------- | --------------- | ---------------- |
| Priority Queue Smallest Range | O(n log k)      | O(k)             |

Explanation

Intial Thoughts

To solve this problem, we should first consider how to compare ranges and determine which one is smaller. We should also think about how to efficiently select numbers from each list to minimize the range. Key points include understanding the definition of a smaller range, recognizing the need to track the maximum value seen so far, and realizing the importance of using a data structure like a priority queue to efficiently select the smallest number from the current options in each list. Additionally, we should consider how to update the smallest range as we process numbers from each list. We need to identify the conditions under which we update the range and ensure that we stop when we can no longer make progress.

Intuitive Analysis

Intuitively, solving this problem involves maintaining a balance between minimizing the range and ensuring that we include at least one number from each list. This can be achieved by always selecting the smallest available number from the lists and then updating the range if necessary. We should imagine the process as a continuous selection and updating process, where we keep track of the maximum value seen and the current smallest range. The use of a priority queue helps in making this selection process efficient by always giving us the smallest number to consider next. By thinking about the problem in this way, we can develop an algorithm that efficiently finds the smallest range.

1. Intuition

• The problem can be approached by maintaining a min-heap of the current smallest elements from each list, along with their list and element indices.
• The key insight is to keep track of the maximum value in the current set of elements, as this will help determine the smallest range.
• By always removing the smallest element from the heap and adding the next element from the same list, we ensure that the heap remains balanced and the maximum value is updated correctly.
• The smallest range is updated whenever a new set of elements is considered, and the range with the smallest difference between the maximum and minimum values is kept.
• This approach works because it considers all possible ranges that include at least one element from each list, and it does so in a way that minimizes the range size.
• The time complexity of this solution is O(N log k), where N is the total number of elements across all lists and k is the number of lists.
• The space complexity is O(k), as we need to store the current elements from each list in the heap.

2. Implementation

• The priority_queue is used to store the current smallest elements from each list, with the greater comparator ensuring that the smallest element is always at the top.
• The maxVal variable is used to keep track of the maximum value in the current set of elements, and it is updated whenever a new element is added to the heap.
• The rangeStart and rangeEnd variables are used to store the smallest range found so far, and they are updated whenever a new range is considered.
• The while loop continues until the heap is empty, at which point all possible ranges have been considered.
• Inside the loop, the smallest element is removed from the heap using pq.top() and pq.pop(), and the next element from the same list is added to the heap using pq.push().
• The if statement checks whether the current range is smaller than the smallest range found so far, and if so, it updates the rangeStart and rangeEnd variables.
• The return statement returns the smallest range found, which is stored in the rangeStart and rangeEnd variables.

Complexity Analysis

Time Complexity:

• The algorithm iterates over the input lists, and for each list, it inserts the first element into the pq priority queue. This operation takes O(k) time. Then, it enters a loop that continues until it can’t proceed further. Inside the loop, it performs a pq.pop() operation, which takes O(log k) time. It also performs a pq.push() operation, which takes O(log k) time. Since the loop runs n times (where n is the total number of elements across all lists), the overall time complexity is O(n log k). The while (pq.size() == nums.size()) loop condition also affects the number of iterations, making the time complexity dependent on the input lists’ sizes.
• The dominant operation in the algorithm is the insertion and removal of elements from the priority queue (pq.push() and pq.pop()), which takes O(log k) time. The algorithm also performs a constant amount of work for each element in the input lists.
• The Big O classification of O(n log k) is justified because the algorithm’s time complexity grows linearly with the total number of elements (n) and logarithmically with the number of lists (k). This is due to the use of a priority queue, which allows for efficient insertion and removal of elements.

Space Complexity:

• The algorithm uses a priority queue (pq) to store elements from the input lists. The maximum number of elements in the priority queue at any given time is equal to the number of lists (k), so the space complexity is O(k).
• The algorithm also uses a constant amount of space to store the maxVal, rangeStart, and rangeEnd variables, but this does not affect the overall space complexity.
• The space complexity is justified because the algorithm only stores a single element from each list in the priority queue at any given time, resulting in a space complexity that grows linearly with the number of lists (k). The use of a priority queue allows for efficient use of space, making the algorithm suitable for large inputs.

Footnote

This question is rated as Hard difficulty.

Similar Questions: