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 Lower Bound, which you haven’t finished yet.

P2MediumBuilt on Lower Bound~3 min speedrun

Flattened Index Binary Search (Search a 2D Matrix)

Built on

Lower BoundA row-major index maps to a matrix cell, and one guarded look confirms equality after Lower Bound.

The problem

Search a 2D Matrix (LC 74)(opens leetcode.com)

You're given an m x n grid of integers, matrix, with two guarantees: each row is sorted left-to-right (non-decreasing), and every row's first value is bigger than the previous row's last value — so reading the grid row by row, the numbers only ever increase.

Given a target value, decide whether it appears anywhere in matrix.

Your solution must run in O(log(m * n)) time.

Example 1

Input:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

Output:true

Read row by row, the grid is 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60; 3 is there, at matrix[0][1].

Global Matrix Bisection

flat indices [0, m * n) → first cell at least target → guarded equality check

Spot it when: The statement says each row of the matrix is sorted and the first value of each row is larger than the last value of the row before it. It asks whether one value is in the matrix, in O(log(m * n)) time.

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: Every cell before flat index lo is smaller than target, and every cell from flat index hi on is at least target or is past the last cell, so the first cell that is at least target is in [lo, hi].

The first value of each row is larger than the last value of the row before it, so reading the matrix row by row gives one sorted list of m * n values. Do not build that list: flat index i names the cell matrix[i // n][i % n], so pass at_least_target and the range [0, m * n) to binary_search_lower_bound, then check the returned cell for equality. Each row holds n cells, so i // n full rows come before index i, and the cell is i % n places into its own row. The cells never decrease as i grows, so at_least_target is False and then True. If target is in the matrix, the first True cell holds it. If not, that cell holds a larger value, or binary_search_lower_bound returns m * n, which is one past the last cell. The trap is the divisor: use n, the number of columns, not m. A square matrix has m == n and hides the wrong divisor, so the bug appears only on another shape.

See it run

Global Matrix Bisection: Lower Bound on flat indices

lo 0hi 20mid none

The top row reads the matrix row by row. The cell row gives each cell as row,column. The column heading is the flat index i.

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
check True when the cell is at least target
answer the first True, where lo and hi meet

matrix = [[1,3,5,7,9],[11,13,15,17,19],[21,23,25,27,29],[31,33,35,37,39]], target = 23, so m = 4, n = 5. The flat indices are 0 up to 20, and hi = m * n = 20 is one past the last cell.

value

1lo

endhi

cell

0,0

0,1

0,2

0,3

0,4

1,0

1,1

1,2

1,3

1,4

2,0

2,1

2,2

2,3

2,4

3,0

3,1

3,2

3,3

3,4

check

1 / 8

Gotchas1 of 4

The trap
Gotcha 1: Dividing the flat index by the number of rows
Mistake
```
return matrix[i // m][i % m] >= target
```
Fix
```
return matrix[i // n][i % n] >= target
```
What happens: There are n cells per row. On this 3-by-4 matrix, dividing by m = 3 reads the wrong cells. The check eventually asks for row 3, which does not exist.
Example: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 60
Mistake: raises IndexErrorFix: returns True
Gotcha 2: Reading the index m * n before checking the range
Mistake
```
if matrix[i // n][i % n] == target:
```
Fix
```
if i < m * n and matrix[i // n][i % n] == target:
```
What happens: When every value is smaller than target, Lower Bound returns m * n, one past the last cell. The row number m * n // n is m, which is past the last row, so reading the cell raises an IndexError. The range check must come first, so the cell is not read.
Example: matrix = [[1,3,5],[7,9,11]], target = 12
Mistake: raises IndexErrorFix: returns False
Gotcha 3: Using equality as the check
Mistake
```
return matrix[i // n][i % n] == target
```
Fix
```
return matrix[i // n][i % n] >= target
```
What happens: For target = 3, equality gives False, True, False, False, False, False. That row is not False and then True. Round 1: mid = 3, the cell is 7, the check is False, so lo = 4. Round 2: mid = 5, the cell is 11, the check is False, so lo = 6. The loop ends with lo = hi = 6, and 6 < 6 is False. The search never looked at index 1, so it returns False even though the matrix contains 3.
Example: matrix = [[1,3,5],[7,9,11]], target = 3
Mistake: returns FalseFix: returns True
Gotcha 4: Writing > instead of >= in the check
Mistake
```
return matrix[i // n][i % n] > target
```
Fix
```
return matrix[i // n][i % n] >= target
```
What happens: > is False for the cell equal to target, so the search finds the first cell that is larger than target. For target = 3, the checks are False, False, True, True, True, True, and the result is index 2. The cell at index 2 is 5, and 5 is not equal to 3, so the final look returns False.
Example: matrix = [[1,3,5],[7,9,11]], target = 3
Mistake: returns FalseFix: returns True

Not this one if…

Rows and columns are each sorted, but a row can start below the end of the row above, as in Search a 2D Matrix II (LC 240): read row by row it is not one sorted list, so there is no flat index to binary search. See Staircase Search
You need the k-th smallest value, not whether one value is present, and only the rows and columns are sorted, as in Kth Smallest Element in a Sorted Matrix (LC 378). See Kth Smallest

Theory

The question we build

What we know

The matrix has m rows and n columns, so it has m * n cells. A flat index i counts the cells row by row, from 0 to m * n - 1.

What the problem gives us

The statement requires O(log(m * n)) time. A scan reads all m * n cells, and copying the matrix into one list also costs O(m * n) time and memory. So the search must read single cells by their flat index.

The question we build

For matrix = [[1,3,5],[7,9,11]] and target = 3, the cells in flat order are 1, 3, 5, 7, 9, 11. We ask whether each cell is at least 3. The answers are False, True, True, True, True, True. The first True is flat index 1, which names matrix[0][1].

matrix[i // n][i % n]

at_least_target(i)

n = 3, target = 3: flat index 1 names matrix[0][1].

Narrowing down to the template

The candidates are the flat indices 0 to m * n - 1. When no cell is large enough, the answer is m * n. So the call is binary_search_lower_bound(0, m * n, at_least_target), and one equality check follows.

Step 1: Scan every cell

A scan checks each cell for equality.

Step 1: Scan every cellPython

1		def matrix_scan(matrix, target):
2		return any(target in row for row in matrix)

Cost: O(m * n) time and O(1) space.

Step 2: Lower Bound on flat indices

The shared Lower Bound template does the search. The check at_least_target turns i into a cell, and one equality check on the returned index finishes.

Step 2: Lower Bound on flat indicesPython

1		def searchMatrix(matrix: List[List[int]], target: int) -> bool:
2		m, n = len(matrix), len(matrix[0])
3		def at_least_target(i: int) -> bool:
4		return matrix[i // n][i % n] >= target
5
6		lo = 0
7		hi = m * n
8		i = binary_search_lower_bound(lo, hi, at_least_target)
9		if i < m * n and matrix[i // n][i % n] == target:
10		return True
11		return False

Cost: O(log(m * n)) time and O(1) space.

At a larger scale

Each row can be a separate block of storage. Every probe may then cost a separate read, so the design has to keep the number of probes, about log2(m * n), small. Fetch only the rows that a probe needs, never the whole grid.

A very large grid

In Java, C# or C++, a grid with 2³¹ or more cells needs a 64-bit flat index, but LeetCode limits m and n to 100, so this does not happen in Search a 2D Matrix (LC 74).

Real-world use

NumPy's np.unravel_index makes the same translation from a flat position to a row and a column for a row-major array. A sorted file of fixed-size records stored in blocks of n records finds record k in block k // n, at slot k % n. In both cases the flat order is the sorted order, so a binary search over the flat position is correct.

Other ways to solve Search a 2D Matrix (LC 74)

Two searches. A search down the first column picks the row, and a second search looks inside that row. This also takes O(log(m * n)) time. Picking the row is a last-True search for the last row whose first value is at most target, and a target below matrix[0][0] has no such row, which needs its own case. One search on the flat index has no row step.

Walk from the top-right corner. Each comparison drops one row or one column, so the walk takes up to m + n steps. This is the method for Search a 2D Matrix II (LC 240). It is too slow for the O(log(m * n)) limit of this problem.

A grid sorted by columns

The Solve problem uses the same search on a grid sorted column by column. Each column holds m cells, so flat index i is matrix[i % m][i // m]. The divisor is m, the number of rows.

Take matrix = [[1, 10, 23, 40], [3, 11, 30, 50], [5, 16, 34, 60]], so m = 3 and n = 4. Read column by column, the cells are 1, 3, 5, 10, 11, 16, 23, 30, 34, 40, 50, 60.

For target = 30, Lower Bound visits (lo, mid, hi) = (0, 6, 12) False, (7, 9, 12) True, (7, 8, 9) True, (7, 7, 8) True, and returns i = 7. The cell matrix[7 % 3][7 // 3] = matrix[1][2] is 30, so the answer is True.

Only the mapping changes. The loop, the check and the guarded look stay the same.

Say it in an interview

"The first value of each row is larger than the last value of the row before it, so the matrix read row by row is one sorted list. Flat index i names matrix[i // n][i % n], where n is the number of columns, so I never copy the matrix. I pass at_least_target and the range [0, m * n) to Lower Bound, which returns the first cell that is at least target. Then I check i < m * n and compare that one cell with target. The time is O(log(m * n)) and the space is O(1). For a grid sorted by columns, only the mapping changes."

Common Questions

What if a row can start with the same value that the row before it ends with?: The search still works. The cells in row-by-row order never decrease, so at_least_target is still False and then True. With matrix = [[1, 3, 5], [5, 6, 7]] and target = 5, Lower Bound returns the first cell equal to 5, which is flat index 2.
What does the search return when target is smaller than every cell?: at_least_target is True for every index, so Lower Bound returns 0. The cell matrix[0][0] is larger than target, so the final look returns False. This needs no special case.

Practice

Canonical LeetCode:Search a 2D Matrix (LC 74)

The older solution to Search a 2D Matrix (LC 74) keeps a closed range [lo, hi] over the flat index 0 to m * n - 1, and returns as soon as it finds target. This course uses the same template as the 1D search. Lower Bound runs over the flat index range [0, m * n), and one look follows.

The classic loop

Old Way

Python

1	from typing import List
2
3	def search_matrix(matrix: List[List[int]], target: int) -> bool:
4	"""Search a 2D Matrix: Classic Binary Search on the flat row-major index.
5	Time: O(log(M * N)) \| Space: O(1)
6	"""
7	m, n = len(matrix), len(matrix[0])
8	lo, hi = 0, m * n - 1 # Every cell, as one sorted list
9
10	while lo <= hi:
11	mid = lo + (hi - lo) // 2
12	row, col = divmod(mid, n) # n cells per row: divide by n, not m
13	val = matrix[row][col]
14	if val == target:
15	return True
16	elif val < target:
17	lo = mid + 1 # target is further along the list
18	else:
19	hi = mid - 1 # target is earlier in the list
20
21	return False

From the classic loop to our template

Old Way line	In our template	Why
lo, hi = 0, m * n - 1	lo = 0 and hi = m * n	The classic range is closed, so `hi` is the last flat index. The template's `hi` is one past the last flat index.
while lo <= hi:	while lo < hi: (inside the template)	A half-open range is empty when `lo` is equal to `hi`.
row, col = divmod(mid, n) val = matrix[row][col]	at_least_target(i) is matrix[i // n][i % n] >= target	The same cell is read. The check asks if it is at least `target`, and Lower Bound uses the answer.
if val == target: return True	if i < m * n and matrix[i // n][i % n] == target: return True	The classic loop checks for `target` on every pass. The template checks once, after the search, and checks `i < m * n` first.
lo = mid + 1 or hi = mid - 1	lo = mid + 1 or hi = mid (inside the template)	The template keeps `mid` when the check is True, because `mid` may be the first cell that is at least `target`.
return False	return False (after the look)	`False` is returned when the look finds another value, or no cell.

When the classic form is fine

Use it when an interviewer asks for this form, or when the code base already uses it. It can stop early when it finds target, so it may do fewer comparisons for one lookup.

Gotchas of the classic loop

Gotchas1 of 2

The trap
Gotcha 1: Writing divmod(mid, m) instead of divmod(mid, n)
Mistake
```
row, col = divmod(mid, m)
```
Fix
```
row, col = divmod(mid, n)
```
What happens: Each row holds n cells, where n is the number of columns. So flat index mid is in row mid // n, at column mid % n. On a 3 x 4 matrix, flat index 5 is matrix[1][1]. divmod(5, 3) gives (1, 2) and reads matrix[1][2] instead. For target = 60, mid reaches 10, and divmod(10, 3) asks for row 3, which does not exist. A square matrix has m == n, so it hides this mistake.
Example: Search a 2D Matrix (LC 74): matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 60
Mistake: raises IndexErrorFix: returns True
Gotcha 2: Starting hi at m * n instead of m * n - 1
Mistake
```
lo, hi = 0, m * n
```
Fix
```
lo, hi = 0, m * n - 1
```
What happens: The last flat index is m * n - 1. The closed range [lo, hi] reads the cell at hi when lo reaches it. When target is larger than every value, mid reaches m * n. divmod(m * n, n) asks for row m, which does not exist, so Python raises an IndexError.
Example: matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 61
Mistake: raises IndexErrorFix: returns False

Earlier signals

A matrix is sorted along each row and every row starts after the previous row ends, so read row by row it is one sorted list, and you must find a value in log time.

Earlier invariant

If target is in matrix, its flat index is inside [lo, hi], and flat index mid is the cell matrix[mid // n][mid % n].

Earlier description

Because every row starts after the previous row ends, reading matrix row by row gives one sorted list of m * n values, so run Exact Match on that list's positions without building it: lo, hi = 0, m * n - 1, and turn each mid into a cell with row, col = divmod(mid, n). This is correct because position mid has exactly mid // n full rows before it and sits mid % n cells into its own row, so matrix[row][col] is the value the flat list would hold there, and each comparison of val with target drops mid and the half that cannot hold it. The trap is the divisor: it is n, the number of columns (the length of one row), not m. divmod(mid, m) still works on a square matrix, so the bug hides until a non-square one, where it reads the wrong cell or asks for a row that does not exist.

Earlier template

Python

1	from typing import List
2
3	def search_matrix(matrix: List[List[int]], target: int) -> bool:
4	"""Search a 2D Matrix: Classic Binary Search on the flat row-major index.
5	Time: O(log(M * N)) \| Space: O(1)
6	"""
7	m, n = len(matrix), len(matrix[0])
8	lo, hi = 0, m * n - 1 # Every cell, as one sorted list
9
10	while lo <= hi:
11	mid = lo + (hi - lo) // 2
12	row, col = divmod(mid, n) # n cells per row: divide by n, not m
13	val = matrix[row][col]
14	if val == target:
15	return True
16	elif val < target:
17	lo = mid + 1 # target is further along the list
18	else:
19	hi = mid - 1 # target is earlier in the list
20
21	return False

Earlier gotchas

Writing divmod(mid, m) instead of divmod(mid, n)

Each row holds n cells, where n is the number of columns. So flat index mid is in row mid // n, at column mid % n. On a 3 x 4 matrix, flat index 5 is matrix[1][1]. divmod(5, 3) gives (1, 2) and reads matrix[1][2] instead. For target = 60, mid reaches 10, and divmod(10, 3) asks for row 3, which does not exist. A square matrix has m == n, so it hides this mistake.

Starting hi at m * n instead of m * n - 1

The last flat index is m * n - 1. The closed range [lo, hi] reads the cell at hi when lo reaches it. When target is larger than every value, mid reaches m * n. divmod(m * n, n) asks for row m, which does not exist, so Python raises an IndexError.

Picking the row with a separate binary search first

A search down the first column can pick the row, and a second search can look inside that row. This also runs in O(log(m * n)) time. But picking the row is a last-True search. It looks for the last row whose first value is at most target. That search is the Upper Bound card, and it has its own off-by-one risk. For example, a target below matrix[0][0] has no row at all. One search on the flat index has no row step to get wrong.

Walking from the top-right corner

The corner walk starts at the top-right cell. Each comparison drops one row or one column. It is correct, but it takes up to m + n steps. The problem asks for O(log(m * n)) time, which only the binary search meets.

Earlier look-alikes

Rows and columns are each sorted, but a row can start below the end of the row above, as in Search a 2D Matrix II (LC 240): read row by row it is not one sorted list, so there is no flat index to binary search.

You need the k-th smallest value, not whether one value is present, and only the rows and columns are sorted, as in Kth Smallest Element in a Sorted Matrix (LC 378).

Earlier problems

Search a 2D Matrix

Theory Context•Binary Search Boundary

Builds on Lower Bound, which you haven’t finished yet.

P2MediumBuilt on Lower Bound~3 min speedrun

Flattened Index Binary Search (Search a 2D Matrix)

Built on

Lower BoundA row-major index maps to a matrix cell, and one guarded look confirms equality after Lower Bound.

The problem

Search a 2D Matrix (LC 74)(opens leetcode.com)

Given a target value, decide whether it appears anywhere in matrix.

Your solution must run in O(log(m * n)) time.

Example 1

Input:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

Output:true

Read row by row, the grid is 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60; 3 is there, at matrix[0][1].

Global Matrix Bisection

flat indices [0, m * n) → first cell at least target → guarded equality check

Global Matrix Bisection

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

See it run

Global Matrix Bisection: Lower Bound on flat indices

lo 0hi 20mid none

The top row reads the matrix row by row. The cell row gives each cell as row,column. The column heading is the flat index i.

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
check True when the cell is at least target
answer the first True, where lo and hi meet

matrix = [[1,3,5,7,9],[11,13,15,17,19],[21,23,25,27,29],[31,33,35,37,39]], target = 23, so m = 4, n = 5. The flat indices are 0 up to 20, and hi = m * n = 20 is one past the last cell.

value

1lo

endhi

cell

0,0

0,1

0,2

0,3

0,4

1,0

1,1

1,2

1,3

1,4

2,0

2,1

2,2

2,3

2,4

3,0

3,1

3,2

3,3

3,4

check

1 / 8

Gotchas1 of 4

The trap
Gotcha 1: Dividing the flat index by the number of rows
Mistake
```
return matrix[i // m][i % m] >= target
```
Fix
```
return matrix[i // n][i % n] >= target
```
What happens: There are n cells per row. On this 3-by-4 matrix, dividing by m = 3 reads the wrong cells. The check eventually asks for row 3, which does not exist.
Example: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 60
Mistake: raises IndexErrorFix: returns True
Gotcha 2: Reading the index m * n before checking the range
Mistake
```
if matrix[i // n][i % n] == target:
```
Fix
```
if i < m * n and matrix[i // n][i % n] == target:
```
What happens: When every value is smaller than target, Lower Bound returns m * n, one past the last cell. The row number m * n // n is m, which is past the last row, so reading the cell raises an IndexError. The range check must come first, so the cell is not read.
Example: matrix = [[1,3,5],[7,9,11]], target = 12
Mistake: raises IndexErrorFix: returns False
Gotcha 3: Using equality as the check
Mistake
```
return matrix[i // n][i % n] == target
```
Fix
```
return matrix[i // n][i % n] >= target
```
What happens: For target = 3, equality gives False, True, False, False, False, False. That row is not False and then True. Round 1: mid = 3, the cell is 7, the check is False, so lo = 4. Round 2: mid = 5, the cell is 11, the check is False, so lo = 6. The loop ends with lo = hi = 6, and 6 < 6 is False. The search never looked at index 1, so it returns False even though the matrix contains 3.
Example: matrix = [[1,3,5],[7,9,11]], target = 3
Mistake: returns FalseFix: returns True
Gotcha 4: Writing > instead of >= in the check
Mistake
```
return matrix[i // n][i % n] > target
```
Fix
```
return matrix[i // n][i % n] >= target
```
What happens: > is False for the cell equal to target, so the search finds the first cell that is larger than target. For target = 3, the checks are False, False, True, True, True, True, and the result is index 2. The cell at index 2 is 5, and 5 is not equal to 3, so the final look returns False.
Example: matrix = [[1,3,5],[7,9,11]], target = 3
Mistake: returns FalseFix: returns True

Not this one if…

Rows and columns are each sorted, but a row can start below the end of the row above, as in Search a 2D Matrix II (LC 240): read row by row it is not one sorted list, so there is no flat index to binary search. See Staircase Search
You need the k-th smallest value, not whether one value is present, and only the rows and columns are sorted, as in Kth Smallest Element in a Sorted Matrix (LC 378). See Kth Smallest

Theory

The question we build

What we know

The matrix has m rows and n columns, so it has m * n cells. A flat index i counts the cells row by row, from 0 to m * n - 1.

What the problem gives us

The question we build

matrix[i // n][i % n]

at_least_target(i)

n = 3, target = 3: flat index 1 names matrix[0][1].

Narrowing down to the template

Step 1: Scan every cell

A scan checks each cell for equality.

Step 1: Scan every cellPython

1		def matrix_scan(matrix, target):
2		return any(target in row for row in matrix)

Cost: O(m * n) time and O(1) space.

Step 2: Lower Bound on flat indices

The shared Lower Bound template does the search. The check at_least_target turns i into a cell, and one equality check on the returned index finishes.

Step 2: Lower Bound on flat indicesPython

1		def searchMatrix(matrix: List[List[int]], target: int) -> bool:
2		m, n = len(matrix), len(matrix[0])
3		def at_least_target(i: int) -> bool:
4		return matrix[i // n][i % n] >= target
5
6		lo = 0
7		hi = m * n
8		i = binary_search_lower_bound(lo, hi, at_least_target)
9		if i < m * n and matrix[i // n][i % n] == target:
10		return True
11		return False

Cost: O(log(m * n)) time and O(1) space.

At a larger scale

A very large grid

In Java, C# or C++, a grid with 2³¹ or more cells needs a 64-bit flat index, but LeetCode limits m and n to 100, so this does not happen in Search a 2D Matrix (LC 74).

Real-world use

Other ways to solve Search a 2D Matrix (LC 74)

A grid sorted by columns

The Solve problem uses the same search on a grid sorted column by column. Each column holds m cells, so flat index i is matrix[i % m][i // m]. The divisor is m, the number of rows.

Take matrix = [[1, 10, 23, 40], [3, 11, 30, 50], [5, 16, 34, 60]], so m = 3 and n = 4. Read column by column, the cells are 1, 3, 5, 10, 11, 16, 23, 30, 34, 40, 50, 60.

Only the mapping changes. The loop, the check and the guarded look stay the same.

Say it in an interview

"The first value of each row is larger than the last value of the row before it, so the matrix read row by row is one sorted list. Flat index i names matrix[i // n][i % n], where n is the number of columns, so I never copy the matrix. I pass at_least_target and the range [0, m * n) to Lower Bound, which returns the first cell that is at least target. Then I check i < m * n and compare that one cell with target. The time is O(log(m * n)) and the space is O(1). For a grid sorted by columns, only the mapping changes."

Common Questions

What if a row can start with the same value that the row before it ends with?: The search still works. The cells in row-by-row order never decrease, so at_least_target is still False and then True. With matrix = [[1, 3, 5], [5, 6, 7]] and target = 5, Lower Bound returns the first cell equal to 5, which is flat index 2.
What does the search return when target is smaller than every cell?: at_least_target is True for every index, so Lower Bound returns 0. The cell matrix[0][0] is larger than target, so the final look returns False. This needs no special case.

Practice

Canonical LeetCode:Search a 2D Matrix (LC 74)

The classic loop

Old Way

Python

1	from typing import List
2
3	def search_matrix(matrix: List[List[int]], target: int) -> bool:
4	"""Search a 2D Matrix: Classic Binary Search on the flat row-major index.
5	Time: O(log(M * N)) \| Space: O(1)
6	"""
7	m, n = len(matrix), len(matrix[0])
8	lo, hi = 0, m * n - 1 # Every cell, as one sorted list
9
10	while lo <= hi:
11	mid = lo + (hi - lo) // 2
12	row, col = divmod(mid, n) # n cells per row: divide by n, not m
13	val = matrix[row][col]
14	if val == target:
15	return True
16	elif val < target:
17	lo = mid + 1 # target is further along the list
18	else:
19	hi = mid - 1 # target is earlier in the list
20
21	return False

From the classic loop to our template

Old Way line	In our template	Why
lo, hi = 0, m * n - 1	lo = 0 and hi = m * n	The classic range is closed, so `hi` is the last flat index. The template's `hi` is one past the last flat index.
while lo <= hi:	while lo < hi: (inside the template)	A half-open range is empty when `lo` is equal to `hi`.
row, col = divmod(mid, n) val = matrix[row][col]	at_least_target(i) is matrix[i // n][i % n] >= target	The same cell is read. The check asks if it is at least `target`, and Lower Bound uses the answer.
if val == target: return True	if i < m * n and matrix[i // n][i % n] == target: return True	The classic loop checks for `target` on every pass. The template checks once, after the search, and checks `i < m * n` first.
lo = mid + 1 or hi = mid - 1	lo = mid + 1 or hi = mid (inside the template)	The template keeps `mid` when the check is True, because `mid` may be the first cell that is at least `target`.
return False	return False (after the look)	`False` is returned when the look finds another value, or no cell.

When the classic form is fine

Use it when an interviewer asks for this form, or when the code base already uses it. It can stop early when it finds target, so it may do fewer comparisons for one lookup.

Gotchas of the classic loop

Gotchas1 of 2

The trap
Gotcha 1: Writing divmod(mid, m) instead of divmod(mid, n)
Mistake
```
row, col = divmod(mid, m)
```
Fix
```
row, col = divmod(mid, n)
```
What happens: Each row holds n cells, where n is the number of columns. So flat index mid is in row mid // n, at column mid % n. On a 3 x 4 matrix, flat index 5 is matrix[1][1]. divmod(5, 3) gives (1, 2) and reads matrix[1][2] instead. For target = 60, mid reaches 10, and divmod(10, 3) asks for row 3, which does not exist. A square matrix has m == n, so it hides this mistake.
Example: Search a 2D Matrix (LC 74): matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 60
Mistake: raises IndexErrorFix: returns True
Gotcha 2: Starting hi at m * n instead of m * n - 1
Mistake
```
lo, hi = 0, m * n
```
Fix
```
lo, hi = 0, m * n - 1
```
What happens: The last flat index is m * n - 1. The closed range [lo, hi] reads the cell at hi when lo reaches it. When target is larger than every value, mid reaches m * n. divmod(m * n, n) asks for row m, which does not exist, so Python raises an IndexError.
Example: matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 61
Mistake: raises IndexErrorFix: returns False

Earlier signals

A matrix is sorted along each row and every row starts after the previous row ends, so read row by row it is one sorted list, and you must find a value in log time.

Earlier invariant

If target is in matrix, its flat index is inside [lo, hi], and flat index mid is the cell matrix[mid // n][mid % n].

Earlier description

Earlier template

Python

1	from typing import List
2
3	def search_matrix(matrix: List[List[int]], target: int) -> bool:
4	"""Search a 2D Matrix: Classic Binary Search on the flat row-major index.
5	Time: O(log(M * N)) \| Space: O(1)
6	"""
7	m, n = len(matrix), len(matrix[0])
8	lo, hi = 0, m * n - 1 # Every cell, as one sorted list
9
10	while lo <= hi:
11	mid = lo + (hi - lo) // 2
12	row, col = divmod(mid, n) # n cells per row: divide by n, not m
13	val = matrix[row][col]
14	if val == target:
15	return True
16	elif val < target:
17	lo = mid + 1 # target is further along the list
18	else:
19	hi = mid - 1 # target is earlier in the list
20
21	return False

Earlier gotchas

Writing divmod(mid, m) instead of divmod(mid, n)

Starting hi at m * n instead of m * n - 1

Picking the row with a separate binary search first

Walking from the top-right corner

Earlier look-alikes

You need the k-th smallest value, not whether one value is present, and only the rows and columns are sorted, as in Kth Smallest Element in a Sorted Matrix (LC 378).

Earlier problems

Search a 2D Matrix