NeetCode 150 · Heap / Priority Queue

Heap / Priority Queue Problems

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.
01 Easy TreeDesignHeap
Design a class to find the k-th largest element in a stream. Initialize with k and a list of initial numbers.
Test Cases
kl = KthLargest(3, [4,5,8,2]) kl.add(3) → 4 kl.add(5) → 5 kl.add(10) → 8
min-heap size kheappush+heappopO(n log k)
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.
Time: O(log k) per add.
Space: O(k).
02 Easy ArrayHeap
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).
Test Cases
lastStoneWeight([2,7,4,1,8,1]) → 1 lastStoneWeight([1]) → 1
max-heap via negationheapifyO(n log n)
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.
Time: O(n log n).
Space: O(n).
03 Medium ArrayMathHeapSorting
Given array of points on a plane and integer k, return the k closest points to the origin (0,0). Distance = √(x²+y²); no need to sort the output.
Test Cases
kClosest([[1,3],[-2,2]], 1) → [[-2,2]] kClosest([[3,3],[5,-1],[-2,4]], 2) → [[3,3],[-2,4]]
max-heap size knegated distO(n log k)
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.
Time: O(n log k).
Space: O(k).
04 Medium ArrayHeapSortingQuickselect
Given integer array nums and integer k, return the k-th largest element in the array.
Test Cases
findKthLargest([3,2,1,5,6,4], 2) → 5 findKthLargest([3,2,3,1,2,4,5,5,6], 4) → 4
min-heap size knlargestO(n log k)
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.
Time: O(n log k).
Space: O(k).
05 Medium ArrayGreedyHeap
Given CPU tasks and a cooldown n, find the minimum number of intervals to complete all tasks (idle time included).
Test Cases
leastInterval(['A','A','A','B','B','B'], 2) → 8 leastInterval(['A','A','A','B','B','B'], 0) → 6
max frequencyframe formulaCounter
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).
Time: O(n).
Space: O(1).
06 Medium Hash MapHeapDesign
Design a simplified Twitter with postTweet, getNewsFeed (10 most recent from user and followees), follow, and unfollow.
Test Cases
t = Twitter() t.postTweet(1, 5); t.postTweet(1, 3) t.getNewsFeed(1) → [3, 5]
heap for mergedecreasing timestampdefaultdict
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).
07 Hard HeapDesignTwo Pointers
Design a data structure supporting addNum and findMedian. findMedian returns the median of all elements added so far.
Test Cases
mf = MedianFinder() mf.addNum(1); mf.addNum(2) mf.findMedian() → 1.5 mf.addNum(3) mf.findMedian() → 2.0
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.
Time: O(log n) add, O(1) median.
Space: O(n).
← Prev Category Next Category →