Python's heapq is a min-heap. Negate values for a max-heap. Heaps give O(log n) insert/extract and O(1) peek — essential for 'top k' and streaming median problems.
Problems: 7
Easy: 2
Medium: 4
Hard: 1
Learning approach: Read the problem. Try the test cases yourself first.
Click Hint if stuck — it guides without spoiling.
Use Show Solution only after a genuine attempt.
Then hit Let's Code to run your solution live.
Maintain a min-heap of size k. The smallest element in the heap is the k-th largest overall.
Python Solution
import heapq
class KthLargest:
def __init__(self, k, nums):
self.k = k
self.heap = []
for n in nums:
self.add(n)
def add(self, val):
heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap) # remove smallest, keep k largest
return self.heap[0] # smallest of the k largest = k-th largest
Key idea: A min-heap of exactly k elements. The root (minimum) is the k-th largest. When adding, if the heap exceeds size k, pop the minimum. The root is always the answer.
Given stone weights, smash the two heaviest stones. If equal they both destroy; if not, the smaller is destroyed and the larger continues with reduced weight. Return the last stone's weight (or 0).
Python's heapq is a min-heap. Negate values to simulate a max-heap.
Python Solution
import heapq
def lastStoneWeight(stones):
heap = [-s for s in stones] # negate for max-heap
heapq.heapify(heap)
while len(heap) > 1:
y = -heapq.heappop(heap) # heaviest
x = -heapq.heappop(heap) # second heaviest
if x != y:
heapq.heappush(heap, -(y - x))
return -heap[0] if heap else 0
Key idea: Negate all weights to turn the min-heap into a max-heap. Pop the two largest, compute the result, and push back if non-zero.
Maintain a max-heap of size k. Push (-dist, x, y). Pop when size exceeds k.
Python Solution
import heapq
def kClosest(points, k):
heap = []
for x, y in points:
dist = x * x + y * y
heapq.heappush(heap, (-dist, x, y))
if len(heap) > k:
heapq.heappop(heap) # remove farthest
return [[x, y] for _, x, y in heap]
Key idea: A max-heap of size k. Negate distances so the farthest point is at the top. Whenever heap exceeds k, pop the farthest. Remaining k elements are the closest.
Maintain a min-heap of size k. The root is the k-th largest.
Python Solution
import heapq
def findKthLargest(nums, k):
# Min-heap of size k; root = k-th largest
heap = []
for n in nums:
heapq.heappush(heap, n)
if len(heap) > k:
heapq.heappop(heap)
return heap[0]
Key idea: Keep a min-heap of exactly k elements. After processing all numbers, the root is the smallest of the top-k, which is the k-th largest overall.
The most frequent task determines the schedule. Think about how many 'frames' of size (n+1) are needed.
Python Solution
from collections import Counter
def leastInterval(tasks, n):
freq = Counter(tasks)
max_freq = max(freq.values())
# Count tasks with max frequency
max_count = sum(1 for f in freq.values() if f == max_freq)
# Formula: (max_freq - 1) * (n + 1) + max_count
# But we need at least len(tasks) intervals
return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)
Key idea: The most-frequent task creates a framework of blocks of size (n+1). Total frames = (max_freq-1). Add tasks that tie for max_freq in the last block. The answer is at least len(tasks) (no idle needed if tasks fill all slots).
Store each user's tweets as a list. For getNewsFeed, merge the most recent tweets from the user and all followees using a max-heap (use decreasing timestamps).
Python Solution
import heapq
from collections import defaultdict
class Twitter:
def __init__(self):
self.time = 0
self.tweets = defaultdict(list) # userId → [(time, tweetId)]
self.following = defaultdict(set)
def postTweet(self, userId, tweetId):
self.tweets[userId].append((self.time, tweetId))
self.time -= 1 # decreasing so min-heap gives most recent first
def getNewsFeed(self, userId):
heap = []
users = self.following[userId] | {userId}
for uid in users:
ts = self.tweets[uid]
if ts:
t, tid = ts[-1]
heapq.heappush(heap, (t, tid, uid, len(ts) - 1))
result = []
while heap and len(result) < 10:
t, tid, uid, idx = heapq.heappop(heap)
result.append(tid)
if idx > 0:
t2, tid2 = self.tweets[uid][idx - 1]
heapq.heappush(heap, (t2, tid2, uid, idx - 1))
return result
def follow(self, followerId, followeeId):
self.following[followerId].add(followeeId)
def unfollow(self, followerId, followeeId):
self.following[followerId].discard(followeeId)
Key idea: Use decreasing timestamps so a min-heap naturally returns the most recent tweets first. For getNewsFeed, seed the heap with each relevant user's latest tweet, then merge the streams lazily.
Time: O(k log u) for getNewsFeed (k=10, u=followees). Space: O(tweets).
two heapsbalance invariantO(log n) add, O(1) median
Use two heaps: a max-heap for the lower half and a min-heap for the upper half. Keep them balanced (sizes differ by at most 1).
Python Solution
import heapq
class MedianFinder:
def __init__(self):
self.small = [] # max-heap (negated) — lower half
self.large = [] # min-heap — upper half
def addNum(self, num):
heapq.heappush(self.small, -num)
# Ensure all of small <= all of large
if self.small and self.large and -self.small[0] > self.large[0]:
heapq.heappush(self.large, -heapq.heappop(self.small))
# Balance sizes: small can have at most 1 more element
if len(self.small) > len(self.large) + 1:
heapq.heappush(self.large, -heapq.heappop(self.small))
if len(self.large) > len(self.small):
heapq.heappush(self.small, -heapq.heappop(self.large))
def findMedian(self):
if len(self.small) > len(self.large):
return float(-self.small[0])
return (-self.small[0] + self.large[0]) / 2.0
Key idea: Two heaps: a max-heap (small) holds the lower half; a min-heap (large) holds the upper half. After each insertion, rebalance so sizes differ by at most 1. The median is the top(s) of the heaps.