Smallest Range Covering Elements from K Lists
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
class Solution:
def smallestRange(self, nums: List[List[int]]) -> List[int]:
heap=[]
maxvalue=0
for i in range(len(nums)):
heapq.heappush(heap,[nums[i][0],i,0])
maxvalue=max(maxvalue,nums[i][0])
answer=[heap[0][0],maxvalue]
while True:
_,row,col=heapq.heappop(heap)
if col==len(nums[row])-1:
break
next_num=nums[row][col+1]
heapq.heappush(heap,[next_num,row,col+1])
maxvalue=max(maxvalue,next_num)
if maxvalue-heap[0][0]<answer[1]-answer[0]:
answer=[heap[0][0],maxvalue]
return answerRelated Problems
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().