Heaps problems, grouped by pattern
A heap gives you the smallest or largest item in O(log n) while items keep arriving. It is the standard answer to top-k, kth largest and merging k sorted sources.
When to reach for it
- Top k, kth largest or kth smallest
- Merge k sorted lists or arrays
- Repeatedly take the best remaining option
Mistakes to watch for
- Using a max heap when a size-k min heap is enough
- Comparator overflow with a - b in Java
- Not re-adding the next item from the same source
The 26 problems
1Top K / Kth Largest / Smallest
- Kth Largest Element in an Array Animated Medium
- Kth Largest Element in a Stream Animated Easy
- Top K Frequent Words Medium
- K Closest Points to Origin Medium
- Minimum Cost to Connect Sticks Medium
- High Five Easy
- Remove Stones to Minimize the Total Medium
- Maximum Performance of a Team Hard
- Furthest Building You Can Reach Medium
- Last Stone Weight Easy
- Sort Characters By Frequency Medium
2Composite comparator
- Top K Frequent Elements Animated Medium
- Design Task Manager Medium
- Rank Teams by Votes Medium
- Design Movie Rental System Hard
3Merge K Sorted
- Merge k Sorted Lists Animated Hard
- Merge k Sorted Arrays Animated Medium
- Design Twitter Medium
- Smallest Range Covering Elements from K Lists Hard