Heap Coding Problems: 106 Questions with Solutions
106 heap coding problems — 8 easy · 63 medium · 35 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.
- Problems: 106
- By difficulty: 8 easy · 63 medium · 35 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
A heap (priority queue) hands back the smallest — or largest — element in logarithmic time while new ones keep arriving. The k largest elements, merging sorted streams, scheduling by earliest deadline and running medians are its home ground; these problems practise choosing the heap's key, keeping it bounded at k, and pairing two heaps when the question needs both ends.
New to heap? Read the Heaps and Priority Queues tutorial first.
How heap works, step by step
heap = [2, 5, 3, 7, 9, 6, 8]; push(4); pop()- A min-heap keeps every parent no larger than its children, so the minimum is always at the root. It lives in a plain array: the children of index i sit at 2i + 1 and 2i + 2, and the tree is just a way of reading that array.
- push(4) puts 4 in the next free slot, index 7, so the tree stays complete. Its parent is index (7 − 1) / 2 = 3, holding 7, and 4 < 7 breaks the heap rule there.
- 4 and 7 swap, so 4 rises to index 3 and 7 drops to index 7. Its new parent 5 is still larger, so it keeps climbing.
- 4 and 5 swap, so 4 rises to index 1 and 5 drops to index 3. Its new parent 2 is smaller, so sift-up stops: the heap rule holds again after 2 swaps, at most one per level.
- pop() takes the minimum, 2, from the root. The last value, 7, moves into the root so the tree stays complete, but 7 is larger than its children 4 and 3, so it must sift down.
- 7 swaps with its smaller child, 3 (not 4), so 3 rises and 7 drops to index 2. Its new children are 6 and 8, and one is smaller, so it keeps sinking.
- 7 swaps with its smaller child, 6 (not 8), so 6 rises and 7 drops to index 5. Index 5 has no children inside the heap, so it stops and the minimum 3 is on top. Push and pop each walk one root-to-leaf path: O(log n), and reading the minimum is O(1).
Heap study plan
14 of the 106 Heap problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 92 in the full list below are practice at your own pace. Then move on to Ordered Set.
Day 1
Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.
Day 2
Medium problems: the same pattern with one twist each. Name the twist before you code.
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Task Scheduler Medium
- Meeting Rooms II Medium
Day 4
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 5
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Sort Characters By Frequency Medium
- Ugly Number II Medium
Day 6
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
Day 7
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
- Swim in Rising Water Hard
Day 8
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Heap: the essentials
When to reach for it
"The k largest, smallest, closest or most frequent"; "repeatedly take the best remaining item" — the two heaviest stones, the cheapest next edge, the meeting that ends first; merging k sorted lists; the median of a stream. If the alternative is to sort, take one item, change the data and sort again, a heap does each round in O(log n).
The pattern
For the k largest, keep a min-heap of at most k items: push each new item and pop the smallest whenever the size passes k. The heap then holds the k largest, and its top is the k-th largest. For best-first processing, push candidates as they become available and pop the best. Check which end your library hands back: Python's heapq and Java's PriorityQueue give the smallest, C++'s priority_queue the largest.
import heapq
def kth_largest(nums, k):
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap) # drop the smallest
return heap[0]
Cost
Push and pop are O(log size). A heap capped at k over n items costs O(n log k) time and O(k) space. Building a heap from a whole array at once (heapify) is O(n).
Common mistakes
- Heaping all n items to read the top k: correct, but O(n log n) time and O(n) space.
- Negating keys to get a max-heap and forgetting to negate them back.
- Pushing tuples whose second element cannot be compared: Python compares it when the first ties, so add a counter in between.
- Expecting the heap's array to be sorted; only its top is guaranteed.
Start with
- Last Stone Weight: take the two largest, push back the rest.
- Kth Largest Element in an Array: a heap capped at k.
- Top K Frequent Elements: counts first, then a heap over them.
All heap problems
Easy (8)
- Make Array Zero by Subtracting Equal Amounts Array, Hash Table, Greedy
- Find X-Sum of All K-Long Subarrays I Array, Hash Table, Sliding Window
- Minimum Amount of Time to Fill Cups Array, Greedy, Math
- Take Gifts From the Richest Pile Array, Simulation, Greedy
- The K Weakest Rows in a Matrix Array, Binary Search, Sorting
- Maximum Product of Two Elements in an Array Array, Sorting
- Relative Ranks Array, Sorting
- Last Stone Weight Array
Medium (63)
- Design Task Manager Hash Table, Heap (Priority Queue), Ordered Set
- Design a Food Rating System Array, Hash Table, String
- Design a Number Container System Hash Table, Heap (Priority Queue), Ordered Set
- Smallest Number in Infinite Set Hash Table, Heap (Priority Queue), Ordered Set
- Stock Price Fluctuation Hash Table, Design, Heap (Priority Queue)
- Seat Reservation Manager Heap (Priority Queue), Design
- Design Twitter Hash Table, Heap (Priority Queue), Design
- Kth Largest Sum in a Binary Tree Tree, Breadth-First Search, Sorting
- Max Sum of a Pair With Equal Sum of Digits Array, Hash Table, Sorting
- Power Grid Maintenance Array, Hash Table, Depth-First Search
- Minimum Time to Reach Destination in Directed Graph Graph, Heap (Priority Queue), Shortest Path
- Digit Operations to Make Two Integers Equal Math, Graph, Heap (Priority Queue)
- Find Minimum Time to Reach Last Room II Array, Graph, Heap (Priority Queue)
- Find Minimum Time to Reach Last Room I Array, Graph, Heap (Priority Queue)
- Find a Safe Walk Through a Grid Array, Breadth-First Search, Graph
- Minimum Cost of a Path With Special Roads Array, Graph, Heap (Priority Queue)
- K Highest Ranked Items Within a Price Range Array, Breadth-First Search, Sorting
- Divide Intervals Into Minimum Number of Groups Array, Greedy, Sorting
- Choose K Elements With Maximum Sum Array, Sorting, Heap (Priority Queue)
- Reward Top K Students Hash Table, String, Sorting
- Mark Elements on Array by Performing Queries Array, Hash Table, Sorting
- Remove Stones to Minimize the Total Array, Greedy, Heap (Priority Queue)
- Minimum Number of Seconds to Make Mountain Height Zero Array, Math, Binary Search
- Find Score of an Array After Marking All Elements Array, Hash Table, Sorting
- Construct String With Repeat Limit Hash Table, String, Greedy
- Lexicographically Minimum String After Removing Stars String, Greedy, Heap (Priority Queue)
- Minimum Operations to Exceed Threshold Value II Array, Heap (Priority Queue), Simulation
- Process Tasks Using Servers Array, Simulation, Heap (Priority Queue)
- Maximum Number of Eaten Apples Array, Greedy, Heap (Priority Queue)
- K-th Smallest Prime Fraction Array, Binary Search, Sorting
- Find K Pairs with Smallest Sums Array, Heap (Priority Queue)
- Maximum Subsequence Score Array, Greedy, Sorting
- Total Cost to Hire K Workers Array, Two Pointers, Simulation
- Single-Threaded CPU Array, Sorting, Heap (Priority Queue)
- Number of Orders in the Backlog Array, Simulation, Heap (Priority Queue)
- Maximum Number of Events That Can Be Attended Array, Greedy, Sorting
- The Number of the Smallest Unoccupied Chair Array, Hash Table, Heap (Priority Queue)
- Maximal Score After Applying K Operations Array, Greedy, Heap (Priority Queue)
- Find the Kth Largest Integer in the Array Array, String, Sorting
- Maximum Score From Removing Stones Math, Greedy, Heap (Priority Queue)
- Minimum Cost to Connect Sticks Array, Greedy, Heap (Priority Queue)
- Find the Safest Path in a Grid Array, Matrix, Binary Search
- Maximum Star Sum of a Graph Array, Graph, Greedy
- Super Ugly Number Dynamic Programming, Math
- Maximum Product After K Increments Array, Greedy
- Maximum Total Importance of Roads Graph, Greedy, Sorting
- Path With Minimum Effort Array, Binary Search, Depth-First Search
- Find K Closest Elements Array, Two Pointers, Binary Search
- Kth Smallest Element in a Sorted Matrix Array, Binary Search, Sorting
- Top K Frequent Words Array, Hash Table, String
- K Closest Points to Origin Array, Math, Divide and Conquer
- Reduce Array Size to The Half Array, Hash Table, Greedy
- Ugly Number II Hash Table, Math, Dynamic Programming
- Network Delay Time Graph, Shortest Path
- Course Schedule II Graph, Topological Sort
- Meeting Rooms II Array, Sorting, Intervals
- Sort Characters By Frequency String, Hash Table, Bucket Sort
- Furthest Building You Can Reach Array, Greedy
- Least Number of Unique Integers after K Removals Array, Greedy, Hash Table
- Sort an Array Array, Sorting, Divide and Conquer
- Top K Frequent Elements Array, Hash Table, Bucket Sort
- Kth Largest Element in an Array Array, Quickselect, Sorting
- Task Scheduler Array, Greedy, Counting
Hard (35)
- Sequentially Ordinal Rank Tracker Design, Heap (Priority Queue), Ordered Set
- Design Movie Rental System Array, Hash Table, Heap (Priority Queue)
- Finding MK Average Queue, Heap (Priority Queue), Ordered Set
- Dinner Plate Stacks Hash Table, Stack, Heap (Priority Queue)
- Merge k Sorted Lists Linked List, Divide and Conquer, Heap (Priority Queue)
- Number of Possible Sets of Closing Branches Bit Manipulation, Graph, Heap (Priority Queue)
- Minimum Number of Visited Cells in a Grid Array, Dynamic Programming, Stack
- Minimum Weighted Subgraph With the Required Paths Graph, Shortest Path, Heap (Priority Queue)
- Minimum Moves to Move a Box to Their Target Location Array, Breadth-First Search, Heap (Priority Queue)
- Reachable Nodes In Subdivided Graph Graph, Heap (Priority Queue), Shortest Path
- Cut Off Trees for Golf Event Array, Breadth-First Search, Heap (Priority Queue)
- Pizza With 3n Slices Array, Dynamic Programming, Greedy
- Maximum Spending After Buying Items Array, Greedy, Sorting
- Minimum Difference in Sums After Removal of Elements Array, Dynamic Programming, Heap (Priority Queue)
- Maximum Number of Points From Grid Queries Array, Breadth-First Search, Matrix
- Course Schedule III Array, Greedy, Sorting
- Minimum Interval to Include Each Query Array, Binary Search, Sorting
- The Skyline Problem Array, Divide and Conquer, Heap (Priority Queue)
- Find Building Where Alice and Bob Can Meet Array, Binary Search, Monotonic Stack
- Constrained Subsequence Sum Array, Dynamic Programming, Queue
- Meeting Rooms III Array, Sorting, Simulation
- Smallest Range Covering Elements from K Lists Array, Hash Table, Greedy
- Minimize Deviation in Array Array, Greedy, Heap (Priority Queue)
- Maximum Performance of a Team Array, Greedy, Sorting
- Construct Target Array With Multiple Sums Array, Heap (Priority Queue), Math
- Put Marbles in Bags Array, Greedy, Sorting
- Minimum Time to Visit a Cell In a Grid Array, Matrix, Graph
- Minimum Obstacle Removal to Reach Corner Array, Matrix, Graph
- Number of Restricted Paths From First to Last Node Graph, Dynamic Programming, Shortest Path
- Trapping Rain Water II Array, Matrix, Heap (Priority Queue)
- Minimum Number of Refueling Stops Array, Greedy, Dynamic Programming
- IPO Array, Greedy, Sorting
- Find the Kth Smallest Sum of a Matrix With Sorted Rows Array, Matrix, Binary Search
- Swim in Rising Water Array, Binary Search, Depth-First Search
- Sliding Window Maximum Array, Sliding Window, Monotonic Queue
Companies that ask heap problems
- Amazon 86 problems on heap
- Google 80 problems on heap
- Microsoft 21 problems on heap
- Flipkart 7 problems on heap
- Meta 7 problems on heap
- Uber 7 problems on heap
- Adobe 5 problems on heap
- Atlassian 4 problems on heap
- Twitter 4 problems on heap
- Yelp 4 problems on heap
- Nutanix 3 problems on heap
- Snapchat 3 problems on heap
Next topic: Ordered Set