Search a 2D Matrix Solution

Problem

Given an m × n integer matrix where each row is sorted left-to-right and the first element of every row is greater than the last element of the row above it, determine whether a target value exists anywhere in the matrix.

Example:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Explanation: 3 appears at row 0, column 1.

Counter-example:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Explanation: 13 would fall between 11 and 16 in row 1, but is not present.

Intuition

Because each row is sorted and every row starts where the previous one ends, the entire matrix reads as one continuous sorted sequence if you unfold it row by row. That means a linear scan is wasteful — you can run a single binary search by treating the matrix as a virtual flat array and converting any index back to a row and column with integer division and modulo.

Approach 1 — Brute Force

Scan every cell until the target is found or the matrix is exhausted.

Steps:

For each row, iterate through each value.
If the value equals the target, return true.
If the entire matrix is checked without a match, return false.

1def searchMatrix(matrix: list[list[int]], target: int) -> bool:
2    for row in matrix:
3        for val in row:
4            if val == target:
5                return True
6    return False

Time: O(m × n) — every cell is visited in the worst case.
Space: O(1) — no extra storage.

Approach 2 — Binary Search on Flattened Matrix (Optimal)

Treat the matrix as a virtual sorted array of m × n elements. Binary search over indices 0 to m × n − 1, converting each midpoint to real coordinates.

Steps:

Set lo = 0, hi = m * n - 1.
While lo <= hi, compute mid = lo + (hi - lo) // 2.
Convert mid to coordinates: row = mid // n, col = mid % n.
If matrix[row][col] == target, return true.
If matrix[row][col] < target, set lo = mid + 1; otherwise set hi = mid - 1.
Return false if the loop ends without a match.

1def searchMatrix(matrix: list[list[int]], target: int) -> bool:
2    rows, cols = len(matrix), len(matrix[0])
3    lo, hi = 0, rows * cols - 1
4
5    while lo <= hi:
6        mid = lo + (hi - lo) // 2
7        mid_val = matrix[mid // cols][mid % cols]  # unfold flat index into 2D coordinates
8
9        if mid_val == target:
10            return True
11        elif mid_val < target:
12            lo = mid + 1
13        else:
14            hi = mid - 1
15
16    return False

Time: O(log(m × n)) — one binary search over all m × n elements.
Space: O(1) — only index variables, no extra data structures.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(m × n)	O(1)	Never in practice; useful as an interview baseline to establish before optimizing
Binary Search on Flattened Matrix	O(log(m × n))	O(1)	Whenever rows are fully sorted AND the last element of each row is strictly less than the first element of the next

Common Mistakes

Confusing this with Search a 2D Matrix II: The II variant only guarantees rows and columns are sorted independently — rows do not chain together, so the flat binary search fails. The two problems require completely different approaches.
Setting hi = rows * cols instead of rows * cols - 1: The first midpoint becomes rows * cols / 2, which is valid, but the final iteration can compute mid = rows * cols - 1, then mid / cols could land out of bounds depending on rounding. Always use rows * cols - 1.
Forgetting to convert mid to 2D coordinates: Writing matrix[mid] instead of matrix[mid / cols][mid % cols] is a type error — mid is a virtual flat index, not a row index.
Integer overflow in mid computation: In Java and C++, (lo + hi) / 2 overflows for large matrices when both values are near Integer.MAX_VALUE. Always use lo + (hi - lo) / 2.
Using lo < hi instead of lo <= hi: When exactly one candidate remains, lo == hi; skipping that iteration causes a missed match and a wrong false return.

Search a 2D Matrix — Solution