Skip to main content

Pattern · 19 problems

Heap and Priority Queue Interview Problems

A heap hands you the smallest item fast and lets you keep adding. Top-k problems are its home.

Get the link for your laptop

Free: write the code and run it, no sign-up.

When I reach for it

  • You need the k largest or k smallest items.
  • You repeatedly take the best remaining item.
  • A stream of numbers needs a running median or top element.

Problems, easiest first

3 easy · 10 medium · 6 hard. Open one to read it, then write it in the free editor.

  1. Meeting RoomseasyIntervalsGreedy
  2. Kth Largest Element in a StreameasyTreesDesign
  3. Last Stone WeighteasyArrays & Hashing
  4. Meeting Rooms IImediumIntervalsGreedy
  5. Course SchedulemediumGraphsBFS & DFS
  6. Telemetry: Top K Frequent Error CodesmediumArrays & Hashing
  7. Cheapest Flights Within K StopsmediumGraphsDynamic Programming
  8. Design TwittermediumLinked ListsDesign
  9. K Closest Points to OriginmediumBinary SearchArrays & Hashing
  10. Kth Largest Element in an ArraymediumBinary SearchArrays & Hashing
  11. Min Cost to Connect All PointsmediumGreedyGraphs
  12. Network Delay TimemediumGraphsBFS & DFS
  13. Task SchedulermediumGreedyArrays & Hashing
  14. Find Median from Data StreamhardTwo PointersDesign
  15. Merge K Sorted ListshardLinked Lists
  16. Minimum Interval to Include Each QueryhardIntervalsBinary Search
  17. Swim in Rising WaterhardBinary SearchGraphs
  18. Sliding Window MaximumhardSliding WindowStack
  19. Trapping Rain WaterhardStackTwo Pointers

The idea

To keep the k largest, hold a min-heap of size k. The smallest of that group sits on top, so it is the one you evict.

Python heapq is a min-heap. For a max-heap, push negated values. For tied priorities, push tuples so items never compare directly.

import heapq

heap = []
for x in stream:
    heapq.heappush(heap, x)
    if len(heap) > k:
        heapq.heappop(heap)    # evict the smallest, keep the k largest
return heap[0]                 # the kth largest sits on top
The kth largest item in a stream. Size k keeps the heap small, and the top is the answer. Python shown; the idea carries to every language in the editor.

Where it goes wrong

  • Building a heap of size n when a heap of size k does the job.
  • Forgetting that heapq has no max-heap. Negate the values.
  • Comparing objects with equal priority. Add a tiebreaker to the tuple.

Say this before you type. Say what the heap holds, how big it stays, and what sits on top.

Where Coco comes in

Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.

Questions people ask

Should I use a heap or just sort?
Sorting costs n log n every time. A heap of size k costs n log k, which wins when k is small or the data keeps arriving.
Why a min-heap for the k largest?
The top of a min-heap is the weakest member of your top k. When a better item arrives, you evict that member in one step.

Meet these next

Fin and Coco are characters, not people. strongyes.io is independent. Leo builds it with AI agents.