What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Priority Queue / Heap

Builds on K-Way Merge, which you haven’t finished yet.

P3MediumBuilt on Top-K Heap~3 min speedrun

Best-First Heap Frontier (Kth Smallest in a Sorted Matrix)

Built on

K-Way MergeThe next entry is built from the popped entry (the next cell of its row) instead of being read from a list.

The problem

Kth Smallest Element in a Sorted Matrix (LC 378)(opens leetcode.com)

matrix is an n x n grid whose values never decrease from left to right along a row or from top to bottom down a column. Find the k-th smallest of its n² values, where repeated values each take their own place in the count (in [[1, 1], [1, 2]], the third smallest value is still 1). The solution must use less than O(n²) extra memory, so copying all the values and sorting them is ruled out.

Example 1

Input:matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8

Output:13

Listed in order, the values are 1, 5, 9, 10, 11, 12, 13, 13, 15; counting the two 13s separately, the 8th is 13.

Best-First Heap

sorted rows ➔ min-heap with one candidate per row ➔ pop the smallest, push the next cell of its row

Spot it when: Rows (or lists) are each sorted and you need the k-th smallest value, or the k smallest values, without sorting everything.

Best-First Heap

Python

1	import heapq
2	from typing import Callable, Iterable, List, TypeVar
3
4	Item = TypeVar("Item")
5
6
7	def best_first(seeds: Iterable[Item], expand: Callable[[Item], Iterable[Item]], k: int) -> List[Item]:
8	"""Best-First Heap: the k smallest items reachable from seeds through expand, in order.
9	Each popped item reveals new candidates.
10	seeds are the first candidates. expand(item) lists the candidates that item reveals when it is popped.
11	Items are compared as they are, so put the value first, as in the tuple (value, row, col).
12	Precondition: expand(item) returns only items at least as large as item, and each item is revealed once.
13	S = the seeds. D = the most items one expand call returns. H = the largest heap size, at most S + K * D.
14	T = the cost of one expand call.
15	Time: O(S + K * (T + (D + 1) * log H)) \| Space: O(H) heap + O(K) popped
16	"""
17	heap = list(seeds) # Min-heap of items; heap[0] is always the smallest item on the frontier
18	heapq.heapify(heap)
19	popped: List[Item] = []
20
21	while heap and len(popped) < k:
22	# 1. Pop the Frontier's Global Minimum:
23	# Every candidate not yet revealed is at least as large as the items expand can still produce, so the heap root is the true overall minimum.
24	item = heapq.heappop(heap) # Global minimum of the frontier
25	popped.append(item)
26
27	# 2. Reveal the Candidates It Unlocks:
28	# Only the items expand(item) returns can be smaller than anything still unseen, so only they need to join the frontier.
29	for nxt in expand(item):
30	heapq.heappush(heap, nxt) # Only the items it reveals can be next
31
32	# 3. Return the k Smallest Items Popped:
33	return popped

Invariant: heap holds, for each seeded row with values left, exactly its leftmost unused cell, so heap[0] is the smallest unused value.

Each row is sorted, so a row's smallest unused value is always the cell right after the last one taken from it. Keep exactly one candidate per row in a min-heap: after popping (val, r, c), push only (r, c + 1), and the heap top is always the smallest unused value in the whole matrix. Column 0 is sorted too, so every value in a row below the k-th is at least the k row heads above it: seeding only the first min(n, k) rows is safe, but when the row heads are not sorted you must seed every row. After k - 1 pops the answer is heap[0][0].

See it run

Best-First Heap, step by step

heap [(1, 0, 0), (2, 1, 0), (3, 2, 0), (6, 3, 0)]pops 0 of 9

The first rows are the matrix. The last two rows are the heap array: the value, then the row and column of that value.

in heap a matrix cell whose entry is in the heap now
taken a matrix cell already popped
pop the cell popped in this step
push the entry pushed in this step
twice a cell that would enter the heap a second time
answer the k-th smallest value, on top of the heap

A 4 by 4 sorted matrix with k = 10. The heap is empty, and the loop will pop 9 times.

row 0

1in heap

row 1

2in heap

row 2

3in heap

row 3

6in heap

heap value

heap r,c

0,0

1,0

2,0

3,0

1 / 22

Gotchas1 of 4

The trap
Gotcha 1: Seeding only min(n, k) rows when column 0 is unsorted
Mistake
```
heap = [(matrix[r][0], r, 0) for r in range(min(n, k))]
```
Fix
```
heap = [(matrix[r][0], r, 0) for r in range(n)]
```
What happens: In Kth Smallest Element in a Sorted Matrix (LC 378), column 0 is sorted. So a row below row k has k smaller or equal row heads above it, and it can be left out. If only the rows are sorted, a low row can hold the smallest value. Leaving that row out loses it, so seed every row.
Example: rows sorted, column 0 not sorted: matrix = [[5, 6], [1, 2]], k = 1
Mistake: returns 5Fix: returns 1
Gotcha 2: Pushing the cell below as well as the right neighbour
Mistake
```
if c + 1 < len(matrix[r]):
    heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
if r + 1 < n:
    heapq.heappush(heap, (matrix[r + 1][c], r + 1, c))
```
Fix
```
if c + 1 < len(matrix[r]):
    heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
```
What happens: Every row already has its own candidate in the heap. The cell below is reached again later from its own row. So it enters the heap twice. Each copy uses up one of the k - 1 pops. The loop then stops at a value that is too small.
Example: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8
Mistake: returns 11Fix: returns 13
Gotcha 3: Popping k times and then reading heap[0]
Mistake
```
for _ in range(k):
```
Fix
```
for _ in range(k - 1):
```
What happens: After k - 1 pops, the k-th smallest value is on top of the heap. One more pop removes it. heap[0] is then the (k + 1)-th smallest value. The other correct form pops k times and returns the last popped value.
Example: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 1
Mistake: returns 5Fix: returns 1
Gotcha 4: Pushing (r, c + 1) without checking c + 1 < len(matrix[r])
Mistake
```
heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
```
Fix
```
if c + 1 < len(matrix[r]):
    heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
```
What happens: The last cell of a row has no right neighbour. Reading matrix[r][c + 1] there raises an IndexError. With the check, a finished row pushes nothing and leaves the heap.
Example: matrix = [[1, 2], [3, 4]], k = 4
Mistake: raises IndexErrorFix: returns 4

Not this one if…

k can reach m * n, up to 9 · 10^8, and the table is never stored, as in Kth Smallest Number in Multiplication Table (LC 668), so k pops are far too many. See Kth Smallest
Every element must come out in sorted order, as in Merge k Sorted Lists (LC 23), not only the first k. See K-Way Merge

Deep Dive

The frontier: what the heap holds, and why one neighbour is enough

K-Way Merge already taught one heap entry per sorted source, with the next entry read from the source. This card adds a change: the next entries are built from the popped entry. The source is a matrix or a table of sums, and no list of next values exists.

In Kth Smallest Element in a Sorted Matrix (LC 378) every row is sorted. The heap holds each row's leftmost unused cell as (value, r, c). This set of candidates is called the frontier.

The smallest unused value in the matrix is always on the frontier. A cell not on the frontier lies to the right of a frontier cell of its row, and that cell is not larger than it. So heap[0] is the smallest unused value.

After popping (val, r, c), the only new candidate is (matrix[r][c + 1], r, c + 1). The cell below is in its own row, which already has a candidate. Pushing it would add the same cell twice.

The frontier traced on a 4 by 4 matrix

Take matrix = [[1, 3, 5, 7], [2, 4, 8, 9], [3, 5, 11, 15], [6, 10, 12, 16]] and k = 10. The sorted values are [1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16], so the answer is 8.

The seeds are (1, 0, 0), (2, 1, 0), (3, 2, 0) and (6, 3, 0), because min(n, k) = 4. The loop pops 9 times and yields 1, 2, 3, 3, 4, 5, 5, 6 and 7. After each pop, the right neighbour of the popped cell is pushed.

The first pop is (1, 0, 0). The cell below it is matrix[1][0] = 2, and it is already in the heap as a seed. This is the first trap: pushing the cell below as well as the right neighbour adds cells twice, and every extra copy uses up one of the k - 1 pops.

The two 3s show the tie rule. (3, 0, 1) pops before (3, 2, 0), because Python compares r after val. After 9 pops the heap is [(8, 1, 2), (10, 3, 1), (11, 2, 2)]. The top value is 8, the 10th smallest. The heap never held more than 4 entries.

Why min(n, k) rows are enough, and why there are k - 1 pops

Column 0 of the matrix is sorted. So the head of row r has r row heads above it that are not larger. If r >= k, then k values are not larger than that head, and the k-th smallest value cannot be in row r. Rows from index k onward can be left out of the seed.

With the matrix above and k = 3, only rows 0, 1 and 2 are seeded. The code returns 3, which is the 3rd smallest value. A brute force on 3,000 random sorted matrices gave the same answer as sorting in every case.

When only the rows are sorted and column 0 is not, a low row can hold the smallest value. Then the seed must include every row. For [[5, 6], [1, 2]] and k = 1, seeding one row returns 5, and seeding both rows returns 1.

The loop pops k - 1 times and reads heap[0]. After k - 1 pops, the k-th smallest value is on top. With k = 1, the loop runs zero times and the answer is heap[0][0], the first smallest value. A loop of k pops would remove the answer.

Extension: when a popped cell can reveal two cells (Find K Pairs with Smallest Sums, LC 373)

The matrix version needs no seen set, because a popped cell reveals exactly one cell, its right neighbour. In Find K Pairs with Smallest Sums (LC 373), the sums nums1[i] + nums2[j] form a matrix that is never stored. If the heap starts with only (0, 0), a popped cell (i, j) reveals two cells, (i + 1, j) and (i, j + 1).

The cell (i + 1, j + 1) is then reached from two parents. A seen set holds the cells already pushed, so each cell enters the heap once. For nums1 = [1, 7, 11], nums2 = [2, 4, 6] and k = 9, the set gives the 9 pairs in order after 9 pushes. Without it, [7, 4] appears twice and [7, 6] three times, after 15 pushes.

The other way needs no seen set. Seed (nums1[i] + nums2[0], i, 0) for the first min(k, len(nums1)) values of i, and after each pop push only (i, j + 1). That is the matrix version of this card.

60-Second Pitch

"Each row is sorted, so the smallest unused value of a row is the cell after the last one I took from it. I keep exactly that cell for each row in a min-heap. This set is the frontier. The heap root is then the smallest unused value in the whole matrix. I pop it and push only the right neighbour of the popped cell. The cell below already has a candidate in its own row. I pop k - 1 times, and the k-th smallest value is on top. Column 0 is sorted, so I seed only the first min(n, k) rows. The time is O(k log min(n, k)) and the space is O(min(n, k)). If a popped cell can reveal two cells, as in Find K Pairs with Smallest Sums (LC 373), I add a seen set so no cell enters twice."

Common Questions

Why do you push only the right neighbour and not the cell below?: Every row already has a candidate in the heap. The cell below belongs to its own row, and that row reaches it when the cell to its left is popped. Pushing it now adds it twice, and each copy uses up one pop.
Why is it safe to seed only the first min(n, k) rows?: Column 0 is sorted. A row with index r >= k has k row heads above it that are not larger. So the k-th smallest value is never in that row. If column 0 is not sorted, seed every row.
Why k - 1 pops and not k?: After k - 1 pops the k-th smallest value is on top of the heap, and heap[0][0] reads it. A k-th pop removes it. The other correct form pops k times and returns the last popped value.
What are the time and space complexity?: The heap holds at most min(n, k) entries. Seeding costs O(min(n, k)) with heapify. Each of the k - 1 pops and pushes costs O(log min(n, k)). So the time is O(k log min(n, k)) and the space is O(min(n, k)).
How does Find K Pairs with Smallest Sums (LC 373) differ from the matrix version?: The pairs are never stored, so each popped pair builds its next pairs. If it builds both (i + 1, j) and (i, j + 1), a pair can be reached twice, and a seen set stops the copies. This is an extension of the matrix card. Seeding one pair per row of nums1 and moving only j needs no seen set.

SWE Reasoning

Spot it

Rows or lists are sorted and the question asks for the k-th smallest value, or the k smallest values, as in Kth Smallest Element in a Sorted Matrix (LC 378).
The candidates are not stored. Each one is made from a popped candidate, such as the next cell of its row.
Every candidate is at least as large as the candidate that revealed it.
k is small compared with the number of cells, so k pops are cheap.

The invariant, step by step

Seed the frontier with the leftmost cell of the first min(n, k) rows. Column 0 is sorted, so later rows cannot matter.
Each row is sorted. So the smallest unused cell of a row is the cell right after the last one taken from it.
The heap holds exactly that cell for each seeded row that has values left. Therefore heap[0] is the smallest unused value in the matrix.
Pop (val, r, c). Push only (matrix[r][c + 1], r, c + 1), and only when c + 1 < len(matrix[r]).
Do this k - 1 times. The k-th smallest value is then heap[0][0].

Traps

Pushing the cell below as well. Every row already has its own candidate, so the cell below enters the heap twice. Each copy uses up one pop, and the answer is too small. For k = 8 on [[1, 5, 9], [10, 11, 13], [12, 13, 15]] the result is 11 instead of 13.
Popping k times and then reading heap[0]. The answer was removed by the last pop, and heap[0] is the next value. With k = 1 on the same matrix the result is 5 instead of 1.
No bounds check on c + 1. The last cell of a row has no right neighbour, and matrix[r][c + 1] raises an IndexError.
Seeding only min(n, k) rows when column 0 is not sorted. A low row can hold the smallest value and is lost.
Using this card when k is huge. If k is close to the number of cells, k pops cost almost as much as sorting. Use the binary search on the value instead.

Practice

Canonical LeetCode:Kth Smallest Element in a Sorted Matrix (LC 378)Find K Pairs with Smallest Sums (LC 373)Find the Kth Smallest Sum of a Matrix With Sorted Rows (LC 1439)Range Sum of Sorted Subarray Sums (LC 1508)

Theory Context•Priority Queue / Heap

Builds on K-Way Merge, which you haven’t finished yet.

P3MediumBuilt on Top-K Heap~3 min speedrun

Best-First Heap Frontier (Kth Smallest in a Sorted Matrix)

Built on

K-Way MergeThe next entry is built from the popped entry (the next cell of its row) instead of being read from a list.

The problem

Kth Smallest Element in a Sorted Matrix (LC 378)(opens leetcode.com)

Example 1

Input:matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8

Output:13

Listed in order, the values are 1, 5, 9, 10, 11, 12, 13, 13, 15; counting the two 13s separately, the 8th is 13.

Best-First Heap

sorted rows ➔ min-heap with one candidate per row ➔ pop the smallest, push the next cell of its row

Spot it when: Rows (or lists) are each sorted and you need the k-th smallest value, or the k smallest values, without sorting everything.

Best-First Heap

Python

1	import heapq
2	from typing import Callable, Iterable, List, TypeVar
3
4	Item = TypeVar("Item")
5
6
7	def best_first(seeds: Iterable[Item], expand: Callable[[Item], Iterable[Item]], k: int) -> List[Item]:
8	"""Best-First Heap: the k smallest items reachable from seeds through expand, in order.
9	Each popped item reveals new candidates.
10	seeds are the first candidates. expand(item) lists the candidates that item reveals when it is popped.
11	Items are compared as they are, so put the value first, as in the tuple (value, row, col).
12	Precondition: expand(item) returns only items at least as large as item, and each item is revealed once.
13	S = the seeds. D = the most items one expand call returns. H = the largest heap size, at most S + K * D.
14	T = the cost of one expand call.
15	Time: O(S + K * (T + (D + 1) * log H)) \| Space: O(H) heap + O(K) popped
16	"""
17	heap = list(seeds) # Min-heap of items; heap[0] is always the smallest item on the frontier
18	heapq.heapify(heap)
19	popped: List[Item] = []
20
21	while heap and len(popped) < k:
22	# 1. Pop the Frontier's Global Minimum:
23	# Every candidate not yet revealed is at least as large as the items expand can still produce, so the heap root is the true overall minimum.
24	item = heapq.heappop(heap) # Global minimum of the frontier
25	popped.append(item)
26
27	# 2. Reveal the Candidates It Unlocks:
28	# Only the items expand(item) returns can be smaller than anything still unseen, so only they need to join the frontier.
29	for nxt in expand(item):
30	heapq.heappush(heap, nxt) # Only the items it reveals can be next
31
32	# 3. Return the k Smallest Items Popped:
33	return popped

Invariant: heap holds, for each seeded row with values left, exactly its leftmost unused cell, so heap[0] is the smallest unused value.

See it run

Best-First Heap, step by step

heap [(1, 0, 0), (2, 1, 0), (3, 2, 0), (6, 3, 0)]pops 0 of 9

The first rows are the matrix. The last two rows are the heap array: the value, then the row and column of that value.

in heap a matrix cell whose entry is in the heap now
taken a matrix cell already popped
pop the cell popped in this step
push the entry pushed in this step
twice a cell that would enter the heap a second time
answer the k-th smallest value, on top of the heap

A 4 by 4 sorted matrix with k = 10. The heap is empty, and the loop will pop 9 times.

row 0

1in heap

row 1

2in heap

row 2

3in heap

row 3

6in heap

heap value

heap r,c

0,0

1,0

2,0

3,0

1 / 22

Gotchas1 of 4

The trap
Gotcha 1: Seeding only min(n, k) rows when column 0 is unsorted
Mistake
```
heap = [(matrix[r][0], r, 0) for r in range(min(n, k))]
```
Fix
```
heap = [(matrix[r][0], r, 0) for r in range(n)]
```
What happens: In Kth Smallest Element in a Sorted Matrix (LC 378), column 0 is sorted. So a row below row k has k smaller or equal row heads above it, and it can be left out. If only the rows are sorted, a low row can hold the smallest value. Leaving that row out loses it, so seed every row.
Example: rows sorted, column 0 not sorted: matrix = [[5, 6], [1, 2]], k = 1
Mistake: returns 5Fix: returns 1
Gotcha 2: Pushing the cell below as well as the right neighbour
Mistake
```
if c + 1 < len(matrix[r]):
    heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
if r + 1 < n:
    heapq.heappush(heap, (matrix[r + 1][c], r + 1, c))
```
Fix
```
if c + 1 < len(matrix[r]):
    heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
```
What happens: Every row already has its own candidate in the heap. The cell below is reached again later from its own row. So it enters the heap twice. Each copy uses up one of the k - 1 pops. The loop then stops at a value that is too small.
Example: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8
Mistake: returns 11Fix: returns 13
Gotcha 3: Popping k times and then reading heap[0]
Mistake
```
for _ in range(k):
```
Fix
```
for _ in range(k - 1):
```
What happens: After k - 1 pops, the k-th smallest value is on top of the heap. One more pop removes it. heap[0] is then the (k + 1)-th smallest value. The other correct form pops k times and returns the last popped value.
Example: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 1
Mistake: returns 5Fix: returns 1
Gotcha 4: Pushing (r, c + 1) without checking c + 1 < len(matrix[r])
Mistake
```
heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
```
Fix
```
if c + 1 < len(matrix[r]):
    heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
```
What happens: The last cell of a row has no right neighbour. Reading matrix[r][c + 1] there raises an IndexError. With the check, a finished row pushes nothing and leaves the heap.
Example: matrix = [[1, 2], [3, 4]], k = 4
Mistake: raises IndexErrorFix: returns 4

Not this one if…

k can reach m * n, up to 9 · 10^8, and the table is never stored, as in Kth Smallest Number in Multiplication Table (LC 668), so k pops are far too many. See Kth Smallest
Every element must come out in sorted order, as in Merge k Sorted Lists (LC 23), not only the first k. See K-Way Merge

Deep Dive

The frontier: what the heap holds, and why one neighbour is enough

In Kth Smallest Element in a Sorted Matrix (LC 378) every row is sorted. The heap holds each row's leftmost unused cell as (value, r, c). This set of candidates is called the frontier.

After popping (val, r, c), the only new candidate is (matrix[r][c + 1], r, c + 1). The cell below is in its own row, which already has a candidate. Pushing it would add the same cell twice.

The frontier traced on a 4 by 4 matrix

Take matrix = [[1, 3, 5, 7], [2, 4, 8, 9], [3, 5, 11, 15], [6, 10, 12, 16]] and k = 10. The sorted values are [1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16], so the answer is 8.

Why min(n, k) rows are enough, and why there are k - 1 pops

Extension: when a popped cell can reveal two cells (Find K Pairs with Smallest Sums, LC 373)

60-Second Pitch

Common Questions

Why do you push only the right neighbour and not the cell below?: Every row already has a candidate in the heap. The cell below belongs to its own row, and that row reaches it when the cell to its left is popped. Pushing it now adds it twice, and each copy uses up one pop.
Why is it safe to seed only the first min(n, k) rows?: Column 0 is sorted. A row with index r >= k has k row heads above it that are not larger. So the k-th smallest value is never in that row. If column 0 is not sorted, seed every row.
Why k - 1 pops and not k?: After k - 1 pops the k-th smallest value is on top of the heap, and heap[0][0] reads it. A k-th pop removes it. The other correct form pops k times and returns the last popped value.
What are the time and space complexity?: The heap holds at most min(n, k) entries. Seeding costs O(min(n, k)) with heapify. Each of the k - 1 pops and pushes costs O(log min(n, k)). So the time is O(k log min(n, k)) and the space is O(min(n, k)).
How does Find K Pairs with Smallest Sums (LC 373) differ from the matrix version?: The pairs are never stored, so each popped pair builds its next pairs. If it builds both (i + 1, j) and (i, j + 1), a pair can be reached twice, and a seen set stops the copies. This is an extension of the matrix card. Seeding one pair per row of nums1 and moving only j needs no seen set.

SWE Reasoning

Spot it

Rows or lists are sorted and the question asks for the k-th smallest value, or the k smallest values, as in Kth Smallest Element in a Sorted Matrix (LC 378).
The candidates are not stored. Each one is made from a popped candidate, such as the next cell of its row.
Every candidate is at least as large as the candidate that revealed it.
k is small compared with the number of cells, so k pops are cheap.

The invariant, step by step

Seed the frontier with the leftmost cell of the first min(n, k) rows. Column 0 is sorted, so later rows cannot matter.
Each row is sorted. So the smallest unused cell of a row is the cell right after the last one taken from it.
The heap holds exactly that cell for each seeded row that has values left. Therefore heap[0] is the smallest unused value in the matrix.
Pop (val, r, c). Push only (matrix[r][c + 1], r, c + 1), and only when c + 1 < len(matrix[r]).
Do this k - 1 times. The k-th smallest value is then heap[0][0].

Traps

Pushing the cell below as well. Every row already has its own candidate, so the cell below enters the heap twice. Each copy uses up one pop, and the answer is too small. For k = 8 on [[1, 5, 9], [10, 11, 13], [12, 13, 15]] the result is 11 instead of 13.
Popping k times and then reading heap[0]. The answer was removed by the last pop, and heap[0] is the next value. With k = 1 on the same matrix the result is 5 instead of 1.
No bounds check on c + 1. The last cell of a row has no right neighbour, and matrix[r][c + 1] raises an IndexError.
Seeding only min(n, k) rows when column 0 is not sorted. A low row can hold the smallest value and is lost.
Using this card when k is huge. If k is close to the number of cells, k pops cost almost as much as sorting. Use the binary search on the value instead.

Practice

Theory Context•Priority Queue / Heap

Builds on K-Way Merge, which you haven’t finished yet.

P3MediumBuilt on Top-K Heap~3 min speedrun

Best-First Heap Frontier (Kth Smallest in a Sorted Matrix)

Built on

K-Way MergeThe next entry is built from the popped entry (the next cell of its row) instead of being read from a list.

The problem

Kth Smallest Element in a Sorted Matrix (LC 378)(opens leetcode.com)

Example 1

Input:matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8

Output:13

Listed in order, the values are 1, 5, 9, 10, 11, 12, 13, 13, 15; counting the two 13s separately, the 8th is 13.

Best-First Heap

sorted rows ➔ min-heap with one candidate per row ➔ pop the smallest, push the next cell of its row

Spot it when: Rows (or lists) are each sorted and you need the k-th smallest value, or the k smallest values, without sorting everything.

Best-First Heap

Python

1	import heapq
2	from typing import Callable, Iterable, List, TypeVar
3
4	Item = TypeVar("Item")
5
6
7	def best_first(seeds: Iterable[Item], expand: Callable[[Item], Iterable[Item]], k: int) -> List[Item]:
8	"""Best-First Heap: the k smallest items reachable from seeds through expand, in order.
9	Each popped item reveals new candidates.
10	seeds are the first candidates. expand(item) lists the candidates that item reveals when it is popped.
11	Items are compared as they are, so put the value first, as in the tuple (value, row, col).
12	Precondition: expand(item) returns only items at least as large as item, and each item is revealed once.
13	S = the seeds. D = the most items one expand call returns. H = the largest heap size, at most S + K * D.
14	T = the cost of one expand call.
15	Time: O(S + K * (T + (D + 1) * log H)) \| Space: O(H) heap + O(K) popped
16	"""
17	heap = list(seeds) # Min-heap of items; heap[0] is always the smallest item on the frontier
18	heapq.heapify(heap)
19	popped: List[Item] = []
20
21	while heap and len(popped) < k:
22	# 1. Pop the Frontier's Global Minimum:
23	# Every candidate not yet revealed is at least as large as the items expand can still produce, so the heap root is the true overall minimum.
24	item = heapq.heappop(heap) # Global minimum of the frontier
25	popped.append(item)
26
27	# 2. Reveal the Candidates It Unlocks:
28	# Only the items expand(item) returns can be smaller than anything still unseen, so only they need to join the frontier.
29	for nxt in expand(item):
30	heapq.heappush(heap, nxt) # Only the items it reveals can be next
31
32	# 3. Return the k Smallest Items Popped:
33	return popped

Invariant: heap holds, for each seeded row with values left, exactly its leftmost unused cell, so heap[0] is the smallest unused value.

See it run

Best-First Heap, step by step

heap [(1, 0, 0), (2, 1, 0), (3, 2, 0), (6, 3, 0)]pops 0 of 9

The first rows are the matrix. The last two rows are the heap array: the value, then the row and column of that value.

in heap a matrix cell whose entry is in the heap now
taken a matrix cell already popped
pop the cell popped in this step
push the entry pushed in this step
twice a cell that would enter the heap a second time
answer the k-th smallest value, on top of the heap

A 4 by 4 sorted matrix with k = 10. The heap is empty, and the loop will pop 9 times.

row 0

1in heap

row 1

2in heap

row 2

3in heap

row 3

6in heap

heap value

heap r,c

0,0

1,0

2,0

3,0

1 / 22

Gotchas1 of 4

The trap
Gotcha 1: Seeding only min(n, k) rows when column 0 is unsorted
Mistake
```
heap = [(matrix[r][0], r, 0) for r in range(min(n, k))]
```
Fix
```
heap = [(matrix[r][0], r, 0) for r in range(n)]
```
What happens: In Kth Smallest Element in a Sorted Matrix (LC 378), column 0 is sorted. So a row below row k has k smaller or equal row heads above it, and it can be left out. If only the rows are sorted, a low row can hold the smallest value. Leaving that row out loses it, so seed every row.
Example: rows sorted, column 0 not sorted: matrix = [[5, 6], [1, 2]], k = 1
Mistake: returns 5Fix: returns 1
Gotcha 2: Pushing the cell below as well as the right neighbour
Mistake
```
if c + 1 < len(matrix[r]):
    heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
if r + 1 < n:
    heapq.heappush(heap, (matrix[r + 1][c], r + 1, c))
```
Fix
```
if c + 1 < len(matrix[r]):
    heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
```
What happens: Every row already has its own candidate in the heap. The cell below is reached again later from its own row. So it enters the heap twice. Each copy uses up one of the k - 1 pops. The loop then stops at a value that is too small.
Example: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8
Mistake: returns 11Fix: returns 13
Gotcha 3: Popping k times and then reading heap[0]
Mistake
```
for _ in range(k):
```
Fix
```
for _ in range(k - 1):
```
What happens: After k - 1 pops, the k-th smallest value is on top of the heap. One more pop removes it. heap[0] is then the (k + 1)-th smallest value. The other correct form pops k times and returns the last popped value.
Example: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 1
Mistake: returns 5Fix: returns 1
Gotcha 4: Pushing (r, c + 1) without checking c + 1 < len(matrix[r])
Mistake
```
heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
```
Fix
```
if c + 1 < len(matrix[r]):
    heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
```
What happens: The last cell of a row has no right neighbour. Reading matrix[r][c + 1] there raises an IndexError. With the check, a finished row pushes nothing and leaves the heap.
Example: matrix = [[1, 2], [3, 4]], k = 4
Mistake: raises IndexErrorFix: returns 4

Not this one if…

k can reach m * n, up to 9 · 10^8, and the table is never stored, as in Kth Smallest Number in Multiplication Table (LC 668), so k pops are far too many. See Kth Smallest
Every element must come out in sorted order, as in Merge k Sorted Lists (LC 23), not only the first k. See K-Way Merge

Deep Dive

The frontier: what the heap holds, and why one neighbour is enough

In Kth Smallest Element in a Sorted Matrix (LC 378) every row is sorted. The heap holds each row's leftmost unused cell as (value, r, c). This set of candidates is called the frontier.

After popping (val, r, c), the only new candidate is (matrix[r][c + 1], r, c + 1). The cell below is in its own row, which already has a candidate. Pushing it would add the same cell twice.

The frontier traced on a 4 by 4 matrix

Take matrix = [[1, 3, 5, 7], [2, 4, 8, 9], [3, 5, 11, 15], [6, 10, 12, 16]] and k = 10. The sorted values are [1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16], so the answer is 8.

Why min(n, k) rows are enough, and why there are k - 1 pops

Extension: when a popped cell can reveal two cells (Find K Pairs with Smallest Sums, LC 373)

60-Second Pitch

Common Questions

Why do you push only the right neighbour and not the cell below?: Every row already has a candidate in the heap. The cell below belongs to its own row, and that row reaches it when the cell to its left is popped. Pushing it now adds it twice, and each copy uses up one pop.
Why is it safe to seed only the first min(n, k) rows?: Column 0 is sorted. A row with index r >= k has k row heads above it that are not larger. So the k-th smallest value is never in that row. If column 0 is not sorted, seed every row.
Why k - 1 pops and not k?: After k - 1 pops the k-th smallest value is on top of the heap, and heap[0][0] reads it. A k-th pop removes it. The other correct form pops k times and returns the last popped value.
What are the time and space complexity?: The heap holds at most min(n, k) entries. Seeding costs O(min(n, k)) with heapify. Each of the k - 1 pops and pushes costs O(log min(n, k)). So the time is O(k log min(n, k)) and the space is O(min(n, k)).
How does Find K Pairs with Smallest Sums (LC 373) differ from the matrix version?: The pairs are never stored, so each popped pair builds its next pairs. If it builds both (i + 1, j) and (i, j + 1), a pair can be reached twice, and a seen set stops the copies. This is an extension of the matrix card. Seeding one pair per row of nums1 and moving only j needs no seen set.

SWE Reasoning

Spot it

Rows or lists are sorted and the question asks for the k-th smallest value, or the k smallest values, as in Kth Smallest Element in a Sorted Matrix (LC 378).
The candidates are not stored. Each one is made from a popped candidate, such as the next cell of its row.
Every candidate is at least as large as the candidate that revealed it.
k is small compared with the number of cells, so k pops are cheap.

The invariant, step by step

Seed the frontier with the leftmost cell of the first min(n, k) rows. Column 0 is sorted, so later rows cannot matter.
Each row is sorted. So the smallest unused cell of a row is the cell right after the last one taken from it.
The heap holds exactly that cell for each seeded row that has values left. Therefore heap[0] is the smallest unused value in the matrix.
Pop (val, r, c). Push only (matrix[r][c + 1], r, c + 1), and only when c + 1 < len(matrix[r]).
Do this k - 1 times. The k-th smallest value is then heap[0][0].

Traps

Pushing the cell below as well. Every row already has its own candidate, so the cell below enters the heap twice. Each copy uses up one pop, and the answer is too small. For k = 8 on [[1, 5, 9], [10, 11, 13], [12, 13, 15]] the result is 11 instead of 13.
Popping k times and then reading heap[0]. The answer was removed by the last pop, and heap[0] is the next value. With k = 1 on the same matrix the result is 5 instead of 1.
No bounds check on c + 1. The last cell of a row has no right neighbour, and matrix[r][c + 1] raises an IndexError.
Seeding only min(n, k) rows when column 0 is not sorted. A low row can hold the smallest value and is lost.
Using this card when k is huge. If k is close to the number of cells, k pops cost almost as much as sorting. Use the binary search on the value instead.

Practice

Theory Context•Priority Queue / Heap

Builds on K-Way Merge, which you haven’t finished yet.

P3MediumBuilt on Top-K Heap~3 min speedrun

Best-First Heap Frontier (Kth Smallest in a Sorted Matrix)

Built on

K-Way MergeThe next entry is built from the popped entry (the next cell of its row) instead of being read from a list.

The problem

Kth Smallest Element in a Sorted Matrix (LC 378)(opens leetcode.com)

Example 1

Input:matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8

Output:13

Listed in order, the values are 1, 5, 9, 10, 11, 12, 13, 13, 15; counting the two 13s separately, the 8th is 13.

Best-First Heap

sorted rows ➔ min-heap with one candidate per row ➔ pop the smallest, push the next cell of its row

Spot it when: Rows (or lists) are each sorted and you need the k-th smallest value, or the k smallest values, without sorting everything.

Best-First Heap

Python

1	import heapq
2	from typing import Callable, Iterable, List, TypeVar
3
4	Item = TypeVar("Item")
5
6
7	def best_first(seeds: Iterable[Item], expand: Callable[[Item], Iterable[Item]], k: int) -> List[Item]:
8	"""Best-First Heap: the k smallest items reachable from seeds through expand, in order.
9	Each popped item reveals new candidates.
10	seeds are the first candidates. expand(item) lists the candidates that item reveals when it is popped.
11	Items are compared as they are, so put the value first, as in the tuple (value, row, col).
12	Precondition: expand(item) returns only items at least as large as item, and each item is revealed once.
13	S = the seeds. D = the most items one expand call returns. H = the largest heap size, at most S + K * D.
14	T = the cost of one expand call.
15	Time: O(S + K * (T + (D + 1) * log H)) \| Space: O(H) heap + O(K) popped
16	"""
17	heap = list(seeds) # Min-heap of items; heap[0] is always the smallest item on the frontier
18	heapq.heapify(heap)
19	popped: List[Item] = []
20
21	while heap and len(popped) < k:
22	# 1. Pop the Frontier's Global Minimum:
23	# Every candidate not yet revealed is at least as large as the items expand can still produce, so the heap root is the true overall minimum.
24	item = heapq.heappop(heap) # Global minimum of the frontier
25	popped.append(item)
26
27	# 2. Reveal the Candidates It Unlocks:
28	# Only the items expand(item) returns can be smaller than anything still unseen, so only they need to join the frontier.
29	for nxt in expand(item):
30	heapq.heappush(heap, nxt) # Only the items it reveals can be next
31
32	# 3. Return the k Smallest Items Popped:
33	return popped

Invariant: heap holds, for each seeded row with values left, exactly its leftmost unused cell, so heap[0] is the smallest unused value.

See it run

Best-First Heap, step by step

heap [(1, 0, 0), (2, 1, 0), (3, 2, 0), (6, 3, 0)]pops 0 of 9

The first rows are the matrix. The last two rows are the heap array: the value, then the row and column of that value.

in heap a matrix cell whose entry is in the heap now
taken a matrix cell already popped
pop the cell popped in this step
push the entry pushed in this step
twice a cell that would enter the heap a second time
answer the k-th smallest value, on top of the heap

A 4 by 4 sorted matrix with k = 10. The heap is empty, and the loop will pop 9 times.

row 0

1in heap

row 1

2in heap

row 2

3in heap

row 3

6in heap

heap value

heap r,c

0,0

1,0

2,0

3,0

1 / 22

Gotchas1 of 4

The trap
Gotcha 1: Seeding only min(n, k) rows when column 0 is unsorted
Mistake
```
heap = [(matrix[r][0], r, 0) for r in range(min(n, k))]
```
Fix
```
heap = [(matrix[r][0], r, 0) for r in range(n)]
```
What happens: In Kth Smallest Element in a Sorted Matrix (LC 378), column 0 is sorted. So a row below row k has k smaller or equal row heads above it, and it can be left out. If only the rows are sorted, a low row can hold the smallest value. Leaving that row out loses it, so seed every row.
Example: rows sorted, column 0 not sorted: matrix = [[5, 6], [1, 2]], k = 1
Mistake: returns 5Fix: returns 1
Gotcha 2: Pushing the cell below as well as the right neighbour
Mistake
```
if c + 1 < len(matrix[r]):
    heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
if r + 1 < n:
    heapq.heappush(heap, (matrix[r + 1][c], r + 1, c))
```
Fix
```
if c + 1 < len(matrix[r]):
    heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
```
What happens: Every row already has its own candidate in the heap. The cell below is reached again later from its own row. So it enters the heap twice. Each copy uses up one of the k - 1 pops. The loop then stops at a value that is too small.
Example: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8
Mistake: returns 11Fix: returns 13
Gotcha 3: Popping k times and then reading heap[0]
Mistake
```
for _ in range(k):
```
Fix
```
for _ in range(k - 1):
```
What happens: After k - 1 pops, the k-th smallest value is on top of the heap. One more pop removes it. heap[0] is then the (k + 1)-th smallest value. The other correct form pops k times and returns the last popped value.
Example: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 1
Mistake: returns 5Fix: returns 1
Gotcha 4: Pushing (r, c + 1) without checking c + 1 < len(matrix[r])
Mistake
```
heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
```
Fix
```
if c + 1 < len(matrix[r]):
    heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
```
What happens: The last cell of a row has no right neighbour. Reading matrix[r][c + 1] there raises an IndexError. With the check, a finished row pushes nothing and leaves the heap.
Example: matrix = [[1, 2], [3, 4]], k = 4
Mistake: raises IndexErrorFix: returns 4

Not this one if…

k can reach m * n, up to 9 · 10^8, and the table is never stored, as in Kth Smallest Number in Multiplication Table (LC 668), so k pops are far too many. See Kth Smallest
Every element must come out in sorted order, as in Merge k Sorted Lists (LC 23), not only the first k. See K-Way Merge

Deep Dive

The frontier: what the heap holds, and why one neighbour is enough

In Kth Smallest Element in a Sorted Matrix (LC 378) every row is sorted. The heap holds each row's leftmost unused cell as (value, r, c). This set of candidates is called the frontier.

After popping (val, r, c), the only new candidate is (matrix[r][c + 1], r, c + 1). The cell below is in its own row, which already has a candidate. Pushing it would add the same cell twice.

The frontier traced on a 4 by 4 matrix

Take matrix = [[1, 3, 5, 7], [2, 4, 8, 9], [3, 5, 11, 15], [6, 10, 12, 16]] and k = 10. The sorted values are [1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16], so the answer is 8.

Why min(n, k) rows are enough, and why there are k - 1 pops

Extension: when a popped cell can reveal two cells (Find K Pairs with Smallest Sums, LC 373)

60-Second Pitch

Common Questions

Why do you push only the right neighbour and not the cell below?: Every row already has a candidate in the heap. The cell below belongs to its own row, and that row reaches it when the cell to its left is popped. Pushing it now adds it twice, and each copy uses up one pop.
Why is it safe to seed only the first min(n, k) rows?: Column 0 is sorted. A row with index r >= k has k row heads above it that are not larger. So the k-th smallest value is never in that row. If column 0 is not sorted, seed every row.
Why k - 1 pops and not k?: After k - 1 pops the k-th smallest value is on top of the heap, and heap[0][0] reads it. A k-th pop removes it. The other correct form pops k times and returns the last popped value.
What are the time and space complexity?: The heap holds at most min(n, k) entries. Seeding costs O(min(n, k)) with heapify. Each of the k - 1 pops and pushes costs O(log min(n, k)). So the time is O(k log min(n, k)) and the space is O(min(n, k)).
How does Find K Pairs with Smallest Sums (LC 373) differ from the matrix version?: The pairs are never stored, so each popped pair builds its next pairs. If it builds both (i + 1, j) and (i, j + 1), a pair can be reached twice, and a seen set stops the copies. This is an extension of the matrix card. Seeding one pair per row of nums1 and moving only j needs no seen set.

SWE Reasoning

Spot it

Rows or lists are sorted and the question asks for the k-th smallest value, or the k smallest values, as in Kth Smallest Element in a Sorted Matrix (LC 378).
The candidates are not stored. Each one is made from a popped candidate, such as the next cell of its row.
Every candidate is at least as large as the candidate that revealed it.
k is small compared with the number of cells, so k pops are cheap.

The invariant, step by step

Seed the frontier with the leftmost cell of the first min(n, k) rows. Column 0 is sorted, so later rows cannot matter.
Each row is sorted. So the smallest unused cell of a row is the cell right after the last one taken from it.
The heap holds exactly that cell for each seeded row that has values left. Therefore heap[0] is the smallest unused value in the matrix.
Pop (val, r, c). Push only (matrix[r][c + 1], r, c + 1), and only when c + 1 < len(matrix[r]).
Do this k - 1 times. The k-th smallest value is then heap[0][0].

Traps

Pushing the cell below as well. Every row already has its own candidate, so the cell below enters the heap twice. Each copy uses up one pop, and the answer is too small. For k = 8 on [[1, 5, 9], [10, 11, 13], [12, 13, 15]] the result is 11 instead of 13.
Popping k times and then reading heap[0]. The answer was removed by the last pop, and heap[0] is the next value. With k = 1 on the same matrix the result is 5 instead of 1.
No bounds check on c + 1. The last cell of a row has no right neighbour, and matrix[r][c + 1] raises an IndexError.
Seeding only min(n, k) rows when column 0 is not sorted. A low row can hold the smallest value and is lost.
Using this card when k is huge. If k is close to the number of cells, k pops cost almost as much as sorting. Use the binary search on the value instead.