632. Smallest Range Covering Elements from K Lists
Explanation:
To find the smallest range covering elements from k lists, we can use a sliding window approach. We start by initializing a priority queue to store the current minimum value and its corresponding list index. We then iterate through all the lists simultaneously, maintaining the maximum value among the current elements in the sliding window. At each step, we update the minimum range that covers at least one element from each list. By adjusting the sliding window based on the minimum and maximum values encountered, we can find the smallest range that satisfies the condition.
Algorithmic Idea:
- Initialize a priority queue to store the current minimum value and its list index.
- Initialize a variable to store the maximum value encountered so far.
- Initialize a hashmap to keep track of the count of elements from each list that are included in the current range.
- Iterate through all lists simultaneously and update the sliding window based on the minimum and maximum values.
- Update the minimum range that covers at least one element from each list.
- Repeat until all lists are exhausted.
Time Complexity:
The time complexity of this approach is O(nlogk), where n is the total number of elements across all lists and k is the number of lists.
Space Complexity:
The space complexity of this approach is O(k), where k is the number of lists.
:
class Solution {
public int[] smallestRange(List<List<Integer>> nums) {
PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
int max = Integer.MIN_VALUE;
int rangeStart = 0, rangeEnd = Integer.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));
}
while (minHeap.size() == nums.size()) {
int[] curr = minHeap.poll();
int currVal = curr[0], listIdx = curr[1], elemIdx = curr[2];
if (max - currVal < rangeEnd - rangeStart) {
rangeStart = currVal;
rangeEnd = max;
}
if (elemIdx + 1 < nums.get(listIdx).size()) {
int nextVal = nums.get(listIdx).get(elemIdx + 1);
minHeap.offer(new int[]{nextVal, listIdx, elemIdx + 1});
max = Math.max(max, nextVal);
}
}
return new int[]{rangeStart, rangeEnd};
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.