Search a 2D Matrix: Binary Search on a Flattened Grid

Search a 2D Matrix is LeetCode 74, and it tests whether you can see past the 2D structure to the sorted sequence hiding underneath. Each row is sorted left to right, and the first element of each row is greater than the last element of the previous row. That means the entire matrix, read row by row, forms one long sorted array. Once you notice that, the problem becomes a single binary search.

The problem

You are given an m x n integer matrix where:

• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if the target exists in the matrix, or false otherwise. You must solve it in O(log(m * n)) time.

Example: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3. The answer is true because 3 appears at row 0, column 1.

The matrix has 3 rows and 4 columns, so 12 elements total. Reading row by row gives the sorted sequence [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]. You do not need to actually flatten it. You just need a way to convert between a 1D index and 2D coordinates.

The key insight: virtual flattening

If you stacked the rows end to end, you would get a sorted array of length m * n. Binary search on a sorted array is a solved problem. The only question is how to look up a value at a given 1D index without building the actual flattened array.

The mapping is:

• row = mid // cols
• col = mid % cols

That is it. Given a 1D index mid, you can read matrix[mid // cols][mid % cols] in O(1). No extra space, no preprocessing. You run standard binary search on indices 0 through m * n - 1, and at each step you convert the index to coordinates to read the value.

Visual walkthrough

Searching for target = 3 in the flattened view of [[1,3,5,7],[10,11,16,20],[23,30,34,60]]. At each step, mid is converted to matrix coordinates using row = mid // 4 and col = mid % 4.

Four comparisons to find the target in a 12-element matrix. That is O(log 12), which rounds to about 3.6. Standard binary search, nothing exotic.

The code

Here is the complete Python solution for LeetCode 74:

def searchMatrix(matrix, target):
    rows, cols = len(matrix), len(matrix[0])
    lo, hi = 0, rows * cols - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        val = matrix[mid // cols][mid % cols]

        if val == target:
            return True
        elif val < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return False

The setup computes the total number of elements as rows * cols and sets lo = 0, hi = rows * cols - 1. Those are the bounds of the virtual 1D array.

Inside the loop, mid // cols gives the row and mid % cols gives the column. You read the value from the matrix at those coordinates and compare it to the target. The rest is identical to standard binary search: if the value is too small, move lo up; if too large, move hi down; if equal, return True.

If the loop exits without finding the target, it is not in the matrix.

Complexity analysis

Time: O(log(m * n)). You run binary search on a virtual array of m * n elements. Each iteration does O(1) work (one division, one modulo, one comparison), and the search space halves each time.

Space: O(1). Three variables: lo, hi, mid. You never allocate extra storage. The matrix is read in place through index mapping.

This is optimal. You cannot search a sorted structure of m * n elements faster than O(log(m * n)), and you cannot use less than O(1) auxiliary space.

The building blocks

This problem relies on two reusable building blocks.

Virtual flattening. Any 2D grid stored in row-major order can be treated as a 1D array without copying. The conversion formulas row = index // cols and col = index % cols let you jump between representations in O(1). This shows up whenever you need to binary search, sort, or iterate over a matrix as if it were flat. It also appears in problems like Kth Smallest Element in a Sorted Matrix and Search a 2D Matrix II.

Index-to-coordinate mapping. The formulas mid // cols and mid % cols are the same integer division and modulo you use to convert between 1D and 2D indexing in any context: image processing, board games, memory layouts. Anytime you see a 1D index that needs to address a 2D structure, these two operations are the tool.

# Virtual flattening: 1D index to 2D coordinates
row = index // cols
col = index % cols

# Reading the value
val = matrix[row][col]

Once you have these two building blocks internalized, the entire solution is just "binary search + index mapping." No new algorithmic ideas, just combining two things you already know.

Edge cases to watch for

• Single element: matrix = [[5]], target = 5. lo = hi = mid = 0, matrix[0][0] = 5 = target, return True. Also test with a target that does not match.
• Target not present: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13. Binary search narrows the range until lo > hi and returns False.
• Target is the first element: target = 1. On the first or second iteration, mid lands at index 0, finds the match, and returns early.
• Target is the last element: target = 60. Binary search converges to index 11 (row 2, col 3) and finds it.
• Single row: matrix = [[1,3,5,7]]. This is literally a 1D binary search. The formula still works because mid // 4 is always 0.
• Single column: matrix = [[1],[3],[5]]. cols = 1, so mid // 1 = mid and mid % 1 = 0. You search down the single column.

From understanding to recall

You understand the idea now: flatten virtually, binary search, convert indices. But in an interview, you need to produce the solution without hesitation. The two formulas mid // cols and mid % cols are easy to mix up or second-guess under pressure. Did you divide by rows or columns? Is it row-major or column-major?

Spaced repetition eliminates that uncertainty. You type the solution from scratch today, again tomorrow, then in three days, then a week later. Each repetition reinforces the index mapping until it becomes automatic. After a few rounds, your hands type matrix[mid // cols][mid % cols] without your brain needing to rederive it.

The virtual flattening pattern appears in enough problems that making it second nature pays off well beyond this single question.

Related posts

• Binary Search: More Than Finding a Number - The full guide to binary search patterns, including search on the answer space and boundary variants
• Search in Rotated Sorted Array: Modified Binary Search - Another problem where binary search works on a structure that is not obviously sorted

---

Visual Learner? Master the fundamentals first with our Binary Search Explained visual guide.