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•Binary Search Boundary

Builds on Feasible Function, Staircase Search and Lower Bound, which you haven’t finished yet.

P3HardBuilt on Lower Bound~4 min speedrun

Binary Search on Value Range (Kth Smallest in Sorted Matrix)

Built on

Lower BoundThe check counts the values that are at most the candidate, and the answer is the smallest candidate whose count is at least k.

Grows into

Median of Two Sorted Arrays

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.

Kth Smallest

values you can count ➔ is the count of values at most x at least k? ➔ the first x where it is

Spot it when: The statement asks for the k-th smallest value of items that you can count but not list cheaply, such as a sorted matrix, a multiplication table or the distances between all pairs of an array.

Kth Smallest

Python

1	from typing import Callable, List
2
3
4	def binary_search_lower_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
5	"""First candidate in [lo, hi) where is_feasible is True.
6	Precondition: is_feasible is monotonic (False, False, ..., True, True).
7	Returns hi when no candidate is True. N = hi - lo candidates. T = the cost of one is_feasible call.
8	Time: O(T * log N) \| Space: O(1)
9	"""
10	while lo < hi:
11	mid = lo + (hi - lo) // 2
12
13	# 1. Check the Midpoint:
14	# is_feasible(mid) shows which side of the flip mid is on: before the answer (False),
15	# or at the answer or after it (True).
16	if is_feasible(mid):
17	# 2. Keep the Candidate:
18	# mid may be the first True, so keep it in the range by moving hi down to mid.
19	hi = mid
20	else:
21	# 3. Discard the Candidate:
22	# mid is False, so the first True must be strictly to the right of mid.
23	lo = mid + 1
24
25	# 4. Return the Boundary:
26	# The loop stops when lo equals hi; that position is the first True, or hi when none was True.
27	return lo

Invariant: Fewer than k values are at most lo - 1, and at least k values are at most hi, so the k-th smallest value is from lo to hi.

The number of values that are at most x never goes down when x goes up. So at_least_k_values(x) is False for small x and True from some x on, and the first True is the k-th smallest value. Run Lower Bound over the values, not over the positions, and let a count answer each question. The count changes only at a value that is in the matrix, so the first x that reaches k is always a value of the matrix. The range runs from lo = matrix[0][0] to hi = matrix[-1][-1] + 1, where the count is the total. The trap is return count == k instead of return count >= k. For k = 7, the count is 6 at x = 12 and 8 at x = 13, because 13 appears twice, so the count is never 7. Then the check is never True, and the call returns 16, which is not a value of the matrix.

See it run

Kth Smallest in a Sorted Matrix: Lower Bound over the values

k 3lo 1hi 7mid none

The top row lists every candidate value x. The count row shows, for each tested mid, how many matrix values are at most mid.

lo the first position that can still be the answer
hi the answer is at hi or before it; hi can be one past the end
mid the position the check reads now
lo+mid lo and mid are at the same position
count how many matrix values are at most this mid
answer the first True, where lo and hi meet

matrix = [[1,5],[2,6]] and k = 3. The candidates are the values from lo = 1 up to hi = 7, which is one past the largest value.

1lo

7hi

count

1 / 8

Gotchas1 of 5

The trap
Gotcha 1: Asking for "exactly k" instead of "at least k"
Mistake
```
return count == k
```
Fix
```
return count >= k
```
What happens: The count grows by the number of copies of x, so it can skip k. For k = 7, the count is 6 at x = 12 and 8 at x = 13, because 13 appears twice. The count is never 7, so "exactly 7" is never True. The search then returns hi, which is 16, one past the largest value. The right answer is 13.
Example: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 7
Mistake: returns 16Fix: returns 13
Gotcha 2: Starting the walk at the top-left corner instead of the bottom-left corner
Mistake
```
row, col = 0, 0
```
Fix
```
row, col = rows - 1, 0
```
What happens: From the bottom-left corner, moving up gives a smaller value and moving right gives a larger value, so every move is safe. From the top-left corner, a cell that is at most x adds row + 1 = 1, because no cell is above it. A cell that is larger than x moves row to -1, and the loop ends. The count stays at most cols, so it never reaches k = 8, and the call returns 16.
Example: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8
Mistake: returns 16Fix: returns 13
Gotcha 3: Starting lo at 0 when the values can be negative
Mistake
```
lo = 0
```
Fix
```
lo = matrix[0][0]
```
What happens: The range must hold the answer. When every value is below 0, the range [0, hi) is empty, and the call returns 0. The answer is a negative value. Start at the smallest value of the data.
Example: matrix = [[-5, -4], [-3, -2]], k = 1
Mistake: returns 0Fix: returns -5
Gotcha 4: Counting the values below x with < instead of the values at most x with <=
Mistake
```
if current_value < x:
```
Fix
```
if current_value <= x:
```
What happens: With <, the walk counts only the values below x, so the count at x is too small. The check becomes True one value too late. For matrix = [[1, 5], [2, 6]] and k = 3, the values below 5 are 1 and 2, so the count at 5 is 2 and the check is False. The values below 6 are 1, 2 and 5, so the count at 6 is 3. The call returns 6, but the right answer is 5.
Example: matrix = [[1, 5], [2, 6]], k = 3
Mistake: returns 6Fix: returns 5
Gotcha 5: Searching the positions instead of the values
Mistake
```
lo, hi = 0, rows * cols
```
Fix
```
lo = matrix[0][0]
hi = matrix[-1][-1] + 1
```
What happens: The check counts the values at most x, so x is a value, not a position. For matrix = [[10, 20], [30, 40]] and k = 2, the search runs over the numbers 0 to 4. No value of the matrix is at most any of them, so the count is 0 and the check is never True. The call returns hi, which is 4. The right answer is 20.
Example: matrix = [[10, 20], [30, 40]], k = 2
Mistake: returns 4Fix: returns 20

Not this one if…

You must return the k smallest items themselves, not only the value of the k-th, as in Find K Pairs with Smallest Sums (LC 373): a count below mid never lists them. See Best-First Heap
The answer is the smallest setting (a speed, a capacity) that makes a plan work, as in Koko Eating Bananas (LC 875): there is no rank k to reach. See Feasible Function

Theory

The question we build

What we know

The matrix is sorted along every row and every column. Equal values count separately.

What the problem gives us

The input is a sorted matrix and k. We return the k-th smallest value.

The question we build

For each value x we ask: "are at least k values at most x?" We use matrix = [[1, 5], [2, 6]] and k = 3. Sorted, the values are 1, 2, 5, 6, so the third smallest is 5. The counts for x from 1 to 6 are 1, 2, 2, 2, 3, 4. The answers are False, False, False, False, True, True. The first True is x = 5, which is the answer.

at_least_k_values(x)

The count is 3 first at x = 5. At x = 3 and x = 4 the count stays 2, because no value of the matrix is there.

Narrowing down to the template

The first True is the answer, so the call is binary_search_lower_bound(matrix[0][0], matrix[-1][-1] + 1, at_least_k_values).

Step 1: Sort everything

The k-th smallest value is the value at index k - 1 of the sorted whole. The sort states this in a few lines.

Step 1: Sort everythingPython

1		def kth_smallest_sorted(matrix, k):
2		values = []
3		for row in matrix:
4		for value in row:
5		values.append(value)
6		values.sort()
7		return values[k - 1]

Cost: O(N log N) time and O(N) memory, where N is the number of values. At LeetCode's limit of n = 300, the copy holds 9 * 10⁴ values.

Step 2: Search the values with a count check

Lower Bound needs a check that reads False, then True. The count gives it: at_least_k_values(x) compares the count of values at most x with k. The count comes from the staircase walk of Staircase Search, started at the bottom-left corner. When a cell is at most x, the whole column above it is at most x too, so the walk adds row + 1 and moves right. Otherwise the walk moves up. The search never builds the sorted list. It only counts, for one value at a time.

Step 2: Search the values with a count checkPython

1		def kth_smallest(matrix, k):
2		rows, cols = len(matrix), len(matrix[0])
3
4		def at_least_k_values(x):
5		count = 0
6		row, col = rows - 1, 0 # start at the bottom-left cell
7		while row >= 0 and col < cols:
8		current_value = matrix[row][col]
9		if current_value <= x:
10		# Every entry from the top down to this row in column col is also at most x.
11		count += row + 1
12		col += 1 # move right to check the next column
13		else:
14		row -= 1 # the current value is too large; move up to a smaller value
15		return count >= k
16
17		lo = matrix[0][0] # the smallest value is the top-left cell
18		hi = matrix[-1][-1] + 1 # one past the largest value, which is the bottom-right cell
19		return binary_search_lower_bound(lo, hi, at_least_k_values)

Cost: O((rows + cols) * log(max - min + 2)). Each check is a walk from the bottom-left corner, and it never reads the same cell twice.

Item	Sort everything	Count check
`values.sort()` and `values[k - 1]`	`at_least_k_values` and one Lower Bound call	The sort builds the whole sorted list. The count check never builds it, and it never reads a cell more than once.

The shorter version

The shorter versionPython

1		import bisect
2
3		def kth_smallest_short(matrix, k):
4		rows, cols = len(matrix), len(matrix[0])
5
6		def at_least_k_values(x):
7		count = 0
8		row, col = rows - 1, 0
9		while row >= 0 and col < cols:
10		current_value = matrix[row][col]
11		if current_value <= x:
12		count += row + 1
13		col += 1
14		else:
15		row -= 1
16		return count >= k
17
18		lo, hi = matrix[0][0], matrix[-1][-1] + 1
19		return bisect.bisect_left(range(lo, hi), True, key=at_least_k_values) + lo

range(lo, hi) holds the candidate values. bisect_left returns a position in that range, so + lo turns it back into a value. This form needs Python 3.10 or later, because of key=.

An alternative: one `bisect_right` per row

On one machine, the staircase walk is cheaper: O(rows + cols) for one check, against O(rows * log(cols + 1)) for one bisect_right call per row. But the walk is one sequential pass over adjacent rows and columns, so it cannot be split across machines. A count with bisect_right can be split: each row's count comes from one bisect_right call on that row alone. Each row can live on its own machine, and only that row's count travels across the network.

An alternative: one `bisect_right` per rowPython

1		import bisect
2
3		def kth_smallest_by_row(matrix, k):
4		def at_least_k_values(x):
5		count = 0
6		for row in matrix:
7		count += bisect.bisect_right(row, x) # how many values in this row are at most x
8		return count >= k
9
10		lo = matrix[0][0] # the smallest value is the top-left cell
11		hi = matrix[-1][-1] + 1 # one past the largest value, which is the bottom-right cell
12		return binary_search_lower_bound(lo, hi, at_least_k_values)

bisect_right(row, x) is the number of values in that row that are at most x.

At scale: rows spread across machines

When the rows are spread over many machines, every guess x is one round of requests to every machine. The number of rounds is about log2(max - min), which is about 31 for a range of two billion values. Each round waits for the slowest machine, so the number of rounds matters more than the cost of one bisect_right call inside a machine. A percentile of sharded sorted data is computed in this way: each shard counts the values at most x, and a coordinator searches x without merging the shards.

A second check on the same idea: two sorted lists

Two sorted lists, nums1 and nums2, both not empty. The count is bisect_right(nums1, x) + bisect_right(nums2, x), and the range runs from the smallest value of either list to one past the largest value of either list. The answer is the same as sorting both lists together. The card Median of Two Sorted Arrays builds on this check.

Code / Blueprint

import bisect
 
def kth_of_two_lists(nums1, nums2, k):
    def at_least_k_values(x):
        count = bisect.bisect_right(nums1, x) + bisect.bisect_right(nums2, x)
        return count >= k
 
    lo = min(nums1[0], nums2[0])                # the smallest value of either list
    hi = max(nums1[-1], nums2[-1]) + 1          # one past the largest value of either list
    return binary_search_lower_bound(lo, hi, at_least_k_values)

at_least_k_values(x)

nums1 = [1, 3], nums2 = [2, 4] and k = 3: the count is 3 first at x = 3.

Say it in an interview

A rehearsed way to say the whole approach out loud, in about 60 seconds, for Kth Smallest Element in a Sorted Matrix (LC 378):

"I search the values, not the positions, with Lower Bound from matrix[0][0] to matrix[-1][-1] + 1. The check asks: are at least k values at most x? That count never goes down when x goes up, so the answers are False and then True, and the first True is the k-th smallest value. I count with a walk from the bottom-left corner, in at most rows + cols steps. I use count >= k, never count == k, because the count skips k when a value appears more than once. The time is O((rows + cols) * log(max - min + 2)) and the space is O(1)."

Common Questions

What is the cost, and when is a heap better?: The time is O((rows + cols) * log(max - min + 2)). A heap that pops k times costs O(k log rows). For a small k the heap is simpler. For a large k, such as the median of an n by n matrix, the count search is faster.
How do I get the k-th largest value instead of the k-th smallest?: Ask for the smallest value at position total - k + 1. The k-th largest of total values is the same value as the (total - k + 1)-th smallest, so the same call works with that rank. For [[1, 5], [2, 6]] and the 2nd largest, use k = 4 - 2 + 1 = 3, and the answer is 5.
Which other problems use the same check?: Any problem where you can count the values at most x quickly. Examples are Kth Smallest Number in Multiplication Table (LC 668), Find K-th Smallest Pair Distance (LC 719) and Ugly Number III (LC 1201).

Practice

Canonical LeetCode:Kth Smallest Element in a Sorted Matrix (LC 378)Median of a Row Wise Sorted Matrix (LC 2387)Kth Smallest Number in Multiplication Table (LC 668)Ugly Number III (LC 1201)K-th Smallest Prime Fraction (LC 786)Find K-th Smallest Pair Distance (LC 719)

Quantile Bisection was the name of this card before. Its loop keeps lo and hi as two values, and it counts with sum(...) inside the loop. This course uses the template with the range [lo, hi), and one check function that counts with a plain loop.

The classic loop

Old Way

Python

1	import bisect
2	from typing import List
3
4	def kth_smallest_matrix(matrix: List[List[int]], k: int) -> int:
5	"""Kth Smallest Element in a Sorted Matrix: binary search on the value range, counting with bisect per row.
6	Time: O(R * log(C + 1) * log(max - min + 2)) \| Space: O(1)
7	"""
8	lo, hi = matrix[0][0], matrix[-1][-1]
9
10	while lo < hi:
11	mid = lo + (hi - lo) // 2
12	# Count elements <= mid across all rows
13	count = sum(bisect.bisect_right(row, mid) for row in matrix)
14	if count >= k:
15	hi = mid # mid satisfies rank; try smaller
16	else:
17	lo = mid + 1 # rank not reached; must increase
18
19	return lo

From the classic loop to our template

Old Way line	In our template	Why
lo, hi = matrix[0][0], matrix[-1][-1]	lo = matrix[0][0] and hi = matrix[-1][-1] + 1	The classic range keeps the largest value as `hi`. The template's `hi` is one past the last candidate.
count = sum(bisect.bisect_right(row, mid) for row in matrix)	at_least_k_values(x), with a plain loop over the rows	The same count, written in a check function with a plain loop.
if count >= k: hi = mid else: lo = mid + 1	binary_search_lower_bound(lo, hi, at_least_k_values)	The same loop, written once as the template.

When the classic form is fine

Use it when an interviewer asks for this form, or when the code base already uses it. It is the same loop. The template only gives the loop a name.

Gotchas of the classic loop

Gotchas1 of 5

The trap
Gotcha 1: Writing count > k instead of count >= k
Mistake
```
if count > k:
```
Fix
```
if count >= k:
```
What happens: When exactly k values are at most mid, mid can be the answer. count > k is False there, so the loop sets lo = mid + 1 and moves past the answer. The result is too large.
Example: matrix = [[1, 5], [10, 11]], k = 1
Mistake: returns 5Fix: returns 1
Gotcha 2: Searching positions instead of values
Mistake
```
lo, hi = 0, len(matrix) * len(matrix[0]) - 1
```
Fix
```
lo, hi = matrix[0][0], matrix[-1][-1]
```
What happens: The loop compares mid with the values in the matrix. So lo and hi must be values, from the smallest to the largest. With positions, the search runs over numbers that may not be values in the matrix at all.
Example: matrix = [[10, 20], [30, 40]], k = 2
Mistake: returns 3Fix: returns 20
Gotcha 3: Counting with bisect_left but keeping the same loop
Mistake
```
count = sum(bisect.bisect_left(row, mid) for row in matrix)
```
Fix
```
count = sum(bisect.bisect_right(row, mid) for row in matrix)
```
What happens: bisect_right(row, mid) counts the values less than or equal to mid. bisect_left(row, mid) counts the values strictly less than mid. With bisect_left, this loop finds the smallest mid that has k values below it. That mid is larger than the answer, and it may not be in the matrix. To count with bisect_left, search for the largest mid whose count is still less than k.
Example: matrix = [[1, 5], [10, 11]], k = 1
Mistake: returns 2Fix: returns 1
Gotcha 4: Counting each row with a full scan
Mistake
```
count = sum(sum(1 for x in row if x <= mid) for row in matrix)
```
Fix
```
count = sum(bisect.bisect_right(row, mid) for row in matrix)
```
What happens: A full scan reads every value for every guess, which is O(R · C) per step. bisect_right reads only O(log C) values in each row. In a matrix sorted by rows and by columns, a staircase walk from the bottom-left corner counts in O(R + C). The answer is the same. Only the time changes.
Gotcha 5: Using lo = mid + 1 when the values are fractions
What happens: lo = mid + 1 is correct only for whole numbers, because no whole number lies between mid and mid + 1. Fractions have values between any two numbers. K-th Smallest Prime Fraction (LC 786) needs the Continuous Bisection loop instead.

Earlier signals

You need the k-th smallest value (or the median) of many numbers that are too costly to sort, such as a matrix, a multiplication table or every pair of an array, but for any guess mid you can quickly count how many of them are at most mid.

Earlier invariant

The k-th smallest value is always in [lo, hi]: at least k elements are at most hi, so hi is big enough, and fewer than k elements are at most lo - 1, so every value below lo is too small.

Earlier direction

multi-sequence / row-wise matrix ➔ numeric domain bisection [smallest element, largest element] ➔ rank counting

Earlier description

Don't look for the k-th smallest by its position; guess its value. Binary search the values from matrix[0][0] to matrix[-1][-1], and for each guess mid, count how many elements are at most mid. If count >= k, the k-th smallest is mid or smaller, so keep mid with hi = mid; otherwise it is bigger than mid, so lo = mid + 1. This works because count only grows as mid grows, so the loop stops on the smallest value whose count reaches k, and that value is always a real element: its count reaches k but the count of the value just below it does not, so at least one element equals it exactly. The trap is writing count > k: when exactly k elements are at most the answer, which is the usual case, the search moves past the answer and returns a value that is too big.

Earlier template

Python

1	import bisect
2	from typing import Callable, List
3
4	def kth_smallest(lo: int, hi: int, k: int, count_at_most: Callable[[int], int]) -> int:
5	"""Quantile Bisection: the k-th smallest of many whole numbers, found by binary search on the value.
6	count_at_most(mid) returns how many of the numbers are less than or equal to mid.
7	Precondition: lo is at most the smallest number, hi is at least the largest number, and 1 <= k <= how many numbers there are.
8	R = hi - lo, the size of the value range. T = the cost of one count_at_most call.
9	Time: O(T * log R) \| Space: O(1)
10	"""
11	while lo < hi:
12	mid = lo + (hi - lo) // 2
13	count = count_at_most(mid)
14	if count >= k:
15	hi = mid # mid satisfies rank; try smaller
16	else:
17	lo = mid + 1 # rank not reached; must increase
18
19	return lo # The smallest value whose count reaches k
20
21
22	# Kth Smallest Element in a Sorted Matrix (LC 378): the template above, with lo, hi = matrix[0][0], matrix[-1][-1] and count_at_most(mid) = one bisect_right per row. The step debugger runs this code.
23	def kth_smallest_matrix(matrix: List[List[int]], k: int) -> int:
24	"""Kth Smallest Element in a Sorted Matrix: binary search on the value range, counting with bisect per row.
25	Time: O(R * log C * log(max - min)) \| Space: O(1)
26	"""
27	lo, hi = matrix[0][0], matrix[-1][-1]
28
29	while lo < hi:
30	mid = lo + (hi - lo) // 2
31	# Count elements <= mid across all rows
32	count = sum(bisect.bisect_right(row, mid) for row in matrix)
33	if count >= k:
34	hi = mid # mid satisfies rank; try smaller
35	else:
36	lo = mid + 1 # rank not reached; must increase
37
38	return lo

Earlier gotchas

Writing count > k instead of count >= k

When exactly k values are at most mid, mid can be the answer. count > k is False there, so the loop sets lo = mid + 1 and moves past the answer. The result is too large.

Searching positions instead of values

The loop compares mid with the values in the matrix. So lo and hi must be values, from the smallest to the largest. With positions, the search runs over numbers that may not be values in the matrix at all.

Counting with bisect_left but keeping the same loop

bisect_right(row, mid) counts the values less than or equal to mid. bisect_left(row, mid) counts the values strictly less than mid. With bisect_left, this loop finds the smallest mid that has k values below it. That mid is larger than the answer, and it may not be in the matrix. To count with bisect_left, search for the largest mid whose count is still less than k.

Counting each row with a full scan

A full scan reads every value for every guess, which is O(R · C) per step. bisect_right reads only O(log C) values in each row. In a matrix sorted by rows and by columns, a staircase walk from the bottom-left corner counts in O(R + C). The answer is the same. Only the time changes.

Using lo = mid + 1 when the values are fractions

lo = mid + 1 is correct only for whole numbers, because no whole number lies between mid and mid + 1. Fractions have values between any two numbers. K-th Smallest Prime Fraction (LC 786) needs the Continuous Bisection loop instead.

Earlier look-alikes

You must return the k smallest items themselves, not only the value of the k-th, as in Find K Pairs with Smallest Sums (LC 373): a count below mid never lists them.

The answer is the smallest setting (a speed, a capacity) that makes a plan work, as in Koko Eating Bananas (LC 875): there is no rank k to reach.

Earlier problems

Kth Smallest Element in a Sorted Matrix

Median of a Row Wise Sorted Matrix

Kth Smallest Number in Multiplication Table

Ugly Number III

K-th Smallest Prime Fraction

Find K-th Smallest Pair Distance

Theory Context•Binary Search Boundary

Builds on Feasible Function, Staircase Search and Lower Bound, which you haven’t finished yet.

P3HardBuilt on Lower Bound~4 min speedrun

Binary Search on Value Range (Kth Smallest in Sorted Matrix)

Built on

Lower BoundThe check counts the values that are at most the candidate, and the answer is the smallest candidate whose count is at least k.

Grows into

Median of Two Sorted Arrays

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.

Kth Smallest

values you can count ➔ is the count of values at most x at least k? ➔ the first x where it is

Kth Smallest

Python

1	from typing import Callable, List
2
3
4	def binary_search_lower_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
5	"""First candidate in [lo, hi) where is_feasible is True.
6	Precondition: is_feasible is monotonic (False, False, ..., True, True).
7	Returns hi when no candidate is True. N = hi - lo candidates. T = the cost of one is_feasible call.
8	Time: O(T * log N) \| Space: O(1)
9	"""
10	while lo < hi:
11	mid = lo + (hi - lo) // 2
12
13	# 1. Check the Midpoint:
14	# is_feasible(mid) shows which side of the flip mid is on: before the answer (False),
15	# or at the answer or after it (True).
16	if is_feasible(mid):
17	# 2. Keep the Candidate:
18	# mid may be the first True, so keep it in the range by moving hi down to mid.
19	hi = mid
20	else:
21	# 3. Discard the Candidate:
22	# mid is False, so the first True must be strictly to the right of mid.
23	lo = mid + 1
24
25	# 4. Return the Boundary:
26	# The loop stops when lo equals hi; that position is the first True, or hi when none was True.
27	return lo

Invariant: Fewer than k values are at most lo - 1, and at least k values are at most hi, so the k-th smallest value is from lo to hi.

See it run

Kth Smallest in a Sorted Matrix: Lower Bound over the values

k 3lo 1hi 7mid none

The top row lists every candidate value x. The count row shows, for each tested mid, how many matrix values are at most mid.

lo the first position that can still be the answer
hi the answer is at hi or before it; hi can be one past the end
mid the position the check reads now
lo+mid lo and mid are at the same position
count how many matrix values are at most this mid
answer the first True, where lo and hi meet

matrix = [[1,5],[2,6]] and k = 3. The candidates are the values from lo = 1 up to hi = 7, which is one past the largest value.

1lo

7hi

count

1 / 8

Gotchas1 of 5

The trap
Gotcha 1: Asking for "exactly k" instead of "at least k"
Mistake
```
return count == k
```
Fix
```
return count >= k
```
What happens: The count grows by the number of copies of x, so it can skip k. For k = 7, the count is 6 at x = 12 and 8 at x = 13, because 13 appears twice. The count is never 7, so "exactly 7" is never True. The search then returns hi, which is 16, one past the largest value. The right answer is 13.
Example: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 7
Mistake: returns 16Fix: returns 13
Gotcha 2: Starting the walk at the top-left corner instead of the bottom-left corner
Mistake
```
row, col = 0, 0
```
Fix
```
row, col = rows - 1, 0
```
What happens: From the bottom-left corner, moving up gives a smaller value and moving right gives a larger value, so every move is safe. From the top-left corner, a cell that is at most x adds row + 1 = 1, because no cell is above it. A cell that is larger than x moves row to -1, and the loop ends. The count stays at most cols, so it never reaches k = 8, and the call returns 16.
Example: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8
Mistake: returns 16Fix: returns 13
Gotcha 3: Starting lo at 0 when the values can be negative
Mistake
```
lo = 0
```
Fix
```
lo = matrix[0][0]
```
What happens: The range must hold the answer. When every value is below 0, the range [0, hi) is empty, and the call returns 0. The answer is a negative value. Start at the smallest value of the data.
Example: matrix = [[-5, -4], [-3, -2]], k = 1
Mistake: returns 0Fix: returns -5
Gotcha 4: Counting the values below x with < instead of the values at most x with <=
Mistake
```
if current_value < x:
```
Fix
```
if current_value <= x:
```
What happens: With <, the walk counts only the values below x, so the count at x is too small. The check becomes True one value too late. For matrix = [[1, 5], [2, 6]] and k = 3, the values below 5 are 1 and 2, so the count at 5 is 2 and the check is False. The values below 6 are 1, 2 and 5, so the count at 6 is 3. The call returns 6, but the right answer is 5.
Example: matrix = [[1, 5], [2, 6]], k = 3
Mistake: returns 6Fix: returns 5
Gotcha 5: Searching the positions instead of the values
Mistake
```
lo, hi = 0, rows * cols
```
Fix
```
lo = matrix[0][0]
hi = matrix[-1][-1] + 1
```
What happens: The check counts the values at most x, so x is a value, not a position. For matrix = [[10, 20], [30, 40]] and k = 2, the search runs over the numbers 0 to 4. No value of the matrix is at most any of them, so the count is 0 and the check is never True. The call returns hi, which is 4. The right answer is 20.
Example: matrix = [[10, 20], [30, 40]], k = 2
Mistake: returns 4Fix: returns 20

Not this one if…

You must return the k smallest items themselves, not only the value of the k-th, as in Find K Pairs with Smallest Sums (LC 373): a count below mid never lists them. See Best-First Heap
The answer is the smallest setting (a speed, a capacity) that makes a plan work, as in Koko Eating Bananas (LC 875): there is no rank k to reach. See Feasible Function

Theory

The question we build

What we know

The matrix is sorted along every row and every column. Equal values count separately.

What the problem gives us

The input is a sorted matrix and k. We return the k-th smallest value.

The question we build

at_least_k_values(x)

The count is 3 first at x = 5. At x = 3 and x = 4 the count stays 2, because no value of the matrix is there.

Narrowing down to the template

The first True is the answer, so the call is binary_search_lower_bound(matrix[0][0], matrix[-1][-1] + 1, at_least_k_values).

Step 1: Sort everything

The k-th smallest value is the value at index k - 1 of the sorted whole. The sort states this in a few lines.

Step 1: Sort everythingPython

1		def kth_smallest_sorted(matrix, k):
2		values = []
3		for row in matrix:
4		for value in row:
5		values.append(value)
6		values.sort()
7		return values[k - 1]

Cost: O(N log N) time and O(N) memory, where N is the number of values. At LeetCode's limit of n = 300, the copy holds 9 * 10⁴ values.

Step 2: Search the values with a count check

Step 2: Search the values with a count checkPython

1		def kth_smallest(matrix, k):
2		rows, cols = len(matrix), len(matrix[0])
3
4		def at_least_k_values(x):
5		count = 0
6		row, col = rows - 1, 0 # start at the bottom-left cell
7		while row >= 0 and col < cols:
8		current_value = matrix[row][col]
9		if current_value <= x:
10		# Every entry from the top down to this row in column col is also at most x.
11		count += row + 1
12		col += 1 # move right to check the next column
13		else:
14		row -= 1 # the current value is too large; move up to a smaller value
15		return count >= k
16
17		lo = matrix[0][0] # the smallest value is the top-left cell
18		hi = matrix[-1][-1] + 1 # one past the largest value, which is the bottom-right cell
19		return binary_search_lower_bound(lo, hi, at_least_k_values)

Cost: O((rows + cols) * log(max - min + 2)). Each check is a walk from the bottom-left corner, and it never reads the same cell twice.

Item	Sort everything	Count check
`values.sort()` and `values[k - 1]`	`at_least_k_values` and one Lower Bound call	The sort builds the whole sorted list. The count check never builds it, and it never reads a cell more than once.

The shorter version

The shorter versionPython

1		import bisect
2
3		def kth_smallest_short(matrix, k):
4		rows, cols = len(matrix), len(matrix[0])
5
6		def at_least_k_values(x):
7		count = 0
8		row, col = rows - 1, 0
9		while row >= 0 and col < cols:
10		current_value = matrix[row][col]
11		if current_value <= x:
12		count += row + 1
13		col += 1
14		else:
15		row -= 1
16		return count >= k
17
18		lo, hi = matrix[0][0], matrix[-1][-1] + 1
19		return bisect.bisect_left(range(lo, hi), True, key=at_least_k_values) + lo

range(lo, hi) holds the candidate values. bisect_left returns a position in that range, so + lo turns it back into a value. This form needs Python 3.10 or later, because of key=.

An alternative: one `bisect_right` per row

An alternative: one `bisect_right` per rowPython

1		import bisect
2
3		def kth_smallest_by_row(matrix, k):
4		def at_least_k_values(x):
5		count = 0
6		for row in matrix:
7		count += bisect.bisect_right(row, x) # how many values in this row are at most x
8		return count >= k
9
10		lo = matrix[0][0] # the smallest value is the top-left cell
11		hi = matrix[-1][-1] + 1 # one past the largest value, which is the bottom-right cell
12		return binary_search_lower_bound(lo, hi, at_least_k_values)

bisect_right(row, x) is the number of values in that row that are at most x.

At scale: rows spread across machines

A second check on the same idea: two sorted lists

Code / Blueprint

import bisect
 
def kth_of_two_lists(nums1, nums2, k):
    def at_least_k_values(x):
        count = bisect.bisect_right(nums1, x) + bisect.bisect_right(nums2, x)
        return count >= k
 
    lo = min(nums1[0], nums2[0])                # the smallest value of either list
    hi = max(nums1[-1], nums2[-1]) + 1          # one past the largest value of either list
    return binary_search_lower_bound(lo, hi, at_least_k_values)

at_least_k_values(x)

nums1 = [1, 3], nums2 = [2, 4] and k = 3: the count is 3 first at x = 3.

Say it in an interview

A rehearsed way to say the whole approach out loud, in about 60 seconds, for Kth Smallest Element in a Sorted Matrix (LC 378):

"I search the values, not the positions, with Lower Bound from matrix[0][0] to matrix[-1][-1] + 1. The check asks: are at least k values at most x? That count never goes down when x goes up, so the answers are False and then True, and the first True is the k-th smallest value. I count with a walk from the bottom-left corner, in at most rows + cols steps. I use count >= k, never count == k, because the count skips k when a value appears more than once. The time is O((rows + cols) * log(max - min + 2)) and the space is O(1)."

Common Questions

What is the cost, and when is a heap better?: The time is O((rows + cols) * log(max - min + 2)). A heap that pops k times costs O(k log rows). For a small k the heap is simpler. For a large k, such as the median of an n by n matrix, the count search is faster.
How do I get the k-th largest value instead of the k-th smallest?: Ask for the smallest value at position total - k + 1. The k-th largest of total values is the same value as the (total - k + 1)-th smallest, so the same call works with that rank. For [[1, 5], [2, 6]] and the 2nd largest, use k = 4 - 2 + 1 = 3, and the answer is 5.
Which other problems use the same check?: Any problem where you can count the values at most x quickly. Examples are Kth Smallest Number in Multiplication Table (LC 668), Find K-th Smallest Pair Distance (LC 719) and Ugly Number III (LC 1201).

Practice

The classic loop

Old Way

Python

1	import bisect
2	from typing import List
3
4	def kth_smallest_matrix(matrix: List[List[int]], k: int) -> int:
5	"""Kth Smallest Element in a Sorted Matrix: binary search on the value range, counting with bisect per row.
6	Time: O(R * log(C + 1) * log(max - min + 2)) \| Space: O(1)
7	"""
8	lo, hi = matrix[0][0], matrix[-1][-1]
9
10	while lo < hi:
11	mid = lo + (hi - lo) // 2
12	# Count elements <= mid across all rows
13	count = sum(bisect.bisect_right(row, mid) for row in matrix)
14	if count >= k:
15	hi = mid # mid satisfies rank; try smaller
16	else:
17	lo = mid + 1 # rank not reached; must increase
18
19	return lo

From the classic loop to our template

Old Way line	In our template	Why
lo, hi = matrix[0][0], matrix[-1][-1]	lo = matrix[0][0] and hi = matrix[-1][-1] + 1	The classic range keeps the largest value as `hi`. The template's `hi` is one past the last candidate.
count = sum(bisect.bisect_right(row, mid) for row in matrix)	at_least_k_values(x), with a plain loop over the rows	The same count, written in a check function with a plain loop.
if count >= k: hi = mid else: lo = mid + 1	binary_search_lower_bound(lo, hi, at_least_k_values)	The same loop, written once as the template.

When the classic form is fine

Use it when an interviewer asks for this form, or when the code base already uses it. It is the same loop. The template only gives the loop a name.

Gotchas of the classic loop

Gotchas1 of 5

The trap
Gotcha 1: Writing count > k instead of count >= k
Mistake
```
if count > k:
```
Fix
```
if count >= k:
```
What happens: When exactly k values are at most mid, mid can be the answer. count > k is False there, so the loop sets lo = mid + 1 and moves past the answer. The result is too large.
Example: matrix = [[1, 5], [10, 11]], k = 1
Mistake: returns 5Fix: returns 1
Gotcha 2: Searching positions instead of values
Mistake
```
lo, hi = 0, len(matrix) * len(matrix[0]) - 1
```
Fix
```
lo, hi = matrix[0][0], matrix[-1][-1]
```
What happens: The loop compares mid with the values in the matrix. So lo and hi must be values, from the smallest to the largest. With positions, the search runs over numbers that may not be values in the matrix at all.
Example: matrix = [[10, 20], [30, 40]], k = 2
Mistake: returns 3Fix: returns 20
Gotcha 3: Counting with bisect_left but keeping the same loop
Mistake
```
count = sum(bisect.bisect_left(row, mid) for row in matrix)
```
Fix
```
count = sum(bisect.bisect_right(row, mid) for row in matrix)
```
What happens: bisect_right(row, mid) counts the values less than or equal to mid. bisect_left(row, mid) counts the values strictly less than mid. With bisect_left, this loop finds the smallest mid that has k values below it. That mid is larger than the answer, and it may not be in the matrix. To count with bisect_left, search for the largest mid whose count is still less than k.
Example: matrix = [[1, 5], [10, 11]], k = 1
Mistake: returns 2Fix: returns 1
Gotcha 4: Counting each row with a full scan
Mistake
```
count = sum(sum(1 for x in row if x <= mid) for row in matrix)
```
Fix
```
count = sum(bisect.bisect_right(row, mid) for row in matrix)
```
What happens: A full scan reads every value for every guess, which is O(R · C) per step. bisect_right reads only O(log C) values in each row. In a matrix sorted by rows and by columns, a staircase walk from the bottom-left corner counts in O(R + C). The answer is the same. Only the time changes.
Gotcha 5: Using lo = mid + 1 when the values are fractions
What happens: lo = mid + 1 is correct only for whole numbers, because no whole number lies between mid and mid + 1. Fractions have values between any two numbers. K-th Smallest Prime Fraction (LC 786) needs the Continuous Bisection loop instead.

Earlier signals

Earlier invariant

Earlier direction

multi-sequence / row-wise matrix ➔ numeric domain bisection [smallest element, largest element] ➔ rank counting

Earlier description

Earlier template

Python

1	import bisect
2	from typing import Callable, List
3
4	def kth_smallest(lo: int, hi: int, k: int, count_at_most: Callable[[int], int]) -> int:
5	"""Quantile Bisection: the k-th smallest of many whole numbers, found by binary search on the value.
6	count_at_most(mid) returns how many of the numbers are less than or equal to mid.
7	Precondition: lo is at most the smallest number, hi is at least the largest number, and 1 <= k <= how many numbers there are.
8	R = hi - lo, the size of the value range. T = the cost of one count_at_most call.
9	Time: O(T * log R) \| Space: O(1)
10	"""
11	while lo < hi:
12	mid = lo + (hi - lo) // 2
13	count = count_at_most(mid)
14	if count >= k:
15	hi = mid # mid satisfies rank; try smaller
16	else:
17	lo = mid + 1 # rank not reached; must increase
18
19	return lo # The smallest value whose count reaches k
20
21
22	# Kth Smallest Element in a Sorted Matrix (LC 378): the template above, with lo, hi = matrix[0][0], matrix[-1][-1] and count_at_most(mid) = one bisect_right per row. The step debugger runs this code.
23	def kth_smallest_matrix(matrix: List[List[int]], k: int) -> int:
24	"""Kth Smallest Element in a Sorted Matrix: binary search on the value range, counting with bisect per row.
25	Time: O(R * log C * log(max - min)) \| Space: O(1)
26	"""
27	lo, hi = matrix[0][0], matrix[-1][-1]
28
29	while lo < hi:
30	mid = lo + (hi - lo) // 2
31	# Count elements <= mid across all rows
32	count = sum(bisect.bisect_right(row, mid) for row in matrix)
33	if count >= k:
34	hi = mid # mid satisfies rank; try smaller
35	else:
36	lo = mid + 1 # rank not reached; must increase
37
38	return lo

Earlier gotchas

Writing count > k instead of count >= k

When exactly k values are at most mid, mid can be the answer. count > k is False there, so the loop sets lo = mid + 1 and moves past the answer. The result is too large.

Searching positions instead of values

Counting with bisect_left but keeping the same loop

Counting each row with a full scan

Using lo = mid + 1 when the values are fractions

Earlier look-alikes

You must return the k smallest items themselves, not only the value of the k-th, as in Find K Pairs with Smallest Sums (LC 373): a count below mid never lists them.

The answer is the smallest setting (a speed, a capacity) that makes a plan work, as in Koko Eating Bananas (LC 875): there is no rank k to reach.

Earlier problems

Kth Smallest Element in a Sorted Matrix

Median of a Row Wise Sorted Matrix

Kth Smallest Number in Multiplication Table

Ugly Number III

K-th Smallest Prime Fraction

Find K-th Smallest Pair Distance