Sponsored
Sponsored
In this approach, we use a min-heap to keep track of the smallest element across all lists, and a variable to track the current maximum from the lists. Initially, insert the first element of each list into the heap along with the list index and element index. The range [min, max] is updated as we extract the smallest element from the heap and add the next element from the respective list. The process continues until any one list is exhausted, ensuring the range includes elements from all lists.
Time Complexity: O(n * log k), as each operation on the heap takes O(log k), performed for all elements.
Space Complexity: O(k), where k is the number of lists, due to storage in the heap.
1import heapq
2
3def smallestRange(nums):
4 minHeap = []
5 maxVal = float('-inf')
6 for i in range(len(nums)):
7 heapq.heappush(minHeap, (nums[i][0], i, 0))
8 maxVal = max(maxVal, nums[i][0])
9 rangeStart, rangeEnd = float('-inf'), float('inf')
10 while len(minHeap) == len(nums):
11 minVal, listIndex, elementIndex = heapq.heappop(minHeap)
12 if maxVal - minVal < rangeEnd - rangeStart:
13 rangeStart, rangeEnd = minVal, maxVal
14 if elementIndex + 1 < len(nums[listIndex]):
15 nextVal = nums[listIndex][elementIndex + 1]
16 heapq.heappush(minHeap, (nextVal, listIndex, elementIndex + 1))
17 maxVal = max(maxVal, nextVal)
18 return [rangeStart, rangeEnd]This Python solution uses a min-heap to store the current minimum element along with its list and index. The heapifies the first element of each list and iteratively extracts minimum elements, updating the range when a new smaller range is found. For advanced elements, new entries get pushed into the min-heap. This continues until one list runs out.
In this approach, we maintain an array to store current indices for each list. Similarly, while keeping track of the maximum and minimum values, traverse the lists to update current positions and check the potential range. The update continues as long as all lists contribute a number to the current range.
Time Complexity: O(n * log k) since using a heap.
Space Complexity: O(k) for minimum entries.
1function smallestRange(nums) {
2 constThis JavaScript solution employs a MinPriorityQueue to manage piles with a quick retrieval of minimal entry across lists. With focus on size and substance linkage of current.