Search a 2D Matrix: Flattened Binary Search in O(log(m*n))

Search a 2D Matrix (LeetCode #74) is the gateway problem for search 2d matrix leetcode practice. You are given an m x n matrix where each row is sorted in ascending order and the first element of each row is greater than the last element of the previous row. Given a target value, determine whether it exists in the matrix.

The critical insight is that this matrix is really a sorted array wearing a 2D disguise. Because the rows are sorted and each row continues where the previous one left off, you can treat the entire matrix as a single sorted array of length m * n. That means one binary search solves the whole problem in O(log(m*n)) time and O(1) space.

This problem appears frequently in coding interviews because it tests whether you can see past the 2D structure and apply a fundamental algorithm. Once you learn the flattened-array trick here, it transfers directly to other matrix search problems.

The problem gives you a matrix with two guarantees: each row is sorted left to right in non-decreasing order, and the first integer of each row is strictly greater than the last integer of the previous row. These two constraints together mean the entire matrix, read row by row from top-left to bottom-right, forms one long sorted sequence.

Your task is straightforward: return true if the target exists anywhere in the matrix, or false otherwise. A brute-force scan would check every element in O(m*n) time, but the sorted structure begs for something faster.

Because the data is fully sorted, binary search is the natural tool. The only question is how to apply binary search to a 2D structure — and that is where the flattened array insight comes in.

Imagine unrolling the matrix row by row into a single array. A 3x4 matrix becomes an array of length 12. Index 0 maps to matrix[0][0], index 4 maps to matrix[1][0], and index 11 maps to matrix[2][3]. The entire sequence is sorted, so binary search works directly on it.

You never actually need to create this flattened array. Instead, you use a simple formula to convert any 1D index back into 2D coordinates on the fly. If the matrix has n columns, then for any index mid: row = Math.floor(mid / n) and col = mid % n. This lets you access matrix[row][col] during each binary search step without allocating extra memory.

This approach runs in O(log(m*n)) time — which is the same as O(log m + log n) — and uses O(1) extra space. It is strictly better than the brute-force O(m*n) scan and matches the theoretical lower bound for searching a sorted collection of m*n elements.

The implementation is a textbook binary search with one twist: instead of indexing a flat array, you compute row and column from the mid index. Set lo = 0 and hi = m * n - 1. While lo is less than or equal to hi, compute mid = Math.floor((lo + hi) / 2), convert mid to row and column, and compare matrix[row][col] to the target.

If matrix[row][col] equals the target, return true. If matrix[row][col] is less than the target, move lo = mid + 1. If it is greater, move hi = mid - 1. If the loop exits without finding the target, return false.

In Python, the code is just a few lines. In JavaScript or TypeScript, it looks almost identical. The key point is that this is standard binary search — the only novelty is the index-to-coordinate mapping. No special data structures, no recursion, no edge-case gymnastics.

Consider the matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]] with target = 3. The matrix has m = 3 rows and n = 4 columns, so the flattened array has 12 elements. We search indices 0 through 11.

Step 1: lo = 0, hi = 11, mid = 5. Index 5 maps to row 1, col 1, which is matrix[1][1] = 11. Since 11 > 3, set hi = 4.

Step 2: lo = 0, hi = 4, mid = 2. Index 2 maps to row 0, col 2, which is matrix[0][2] = 5. Since 5 > 3, set hi = 1.

Step 3: lo = 0, hi = 1, mid = 0. Index 0 maps to row 0, col 0, which is matrix[0][0] = 1. Since 1 < 3, set lo = 1.

Step 4: lo = 1, hi = 1, mid = 1. Index 1 maps to row 0, col 1, which is matrix[0][1] = 3. Found the target — return true. The search took only 4 comparisons out of 12 elements, demonstrating the logarithmic efficiency.

A 1x1 matrix is the simplest case: the entire search space is a single element. Your binary search handles this naturally because lo and hi both start at 0, and you compare the single element to the target in one step.

When the target is smaller than matrix[0][0] or larger than matrix[m-1][n-1], the search terminates quickly. The first comparison with the middle element pushes the search boundary in one direction, and the loop exits after O(log(m*n)) steps at most. There is no need for a special early-exit check, though adding one is a minor optimization.

Targets at the very first or very last position of the matrix are found naturally by the binary search. The algorithm does not need special handling for boundary elements. Similarly, duplicate-free rows (which the problem guarantees by specifying strictly increasing order across rows) mean the search is always decisive — each comparison eliminates half the remaining candidates.

The core lesson from this leetcode 74 solution is that sorted 2D structures can be searched as 1D arrays. The index-to-coordinate mapping (row = mid / cols, col = mid % cols) is a technique that appears in many other problems — from matrix rotation to spiral traversal to Kth smallest element in a sorted matrix.

This problem also reinforces the importance of recognizing when binary search applies. Whenever you have a sorted search space — even if it is disguised as a matrix, a rotated array, or a search range — binary search should be your first instinct. The flattened matrix search pattern is just one specific application of this broader principle.

Practice this pattern with YeetCode flashcards to make the index mapping automatic. When you can convert between 1D and 2D coordinates without thinking, you free up mental bandwidth for the harder parts of interview problems. Combine this with the binary search template from LeetCode 704 and the search insert position pattern, and you will have a complete toolkit for sorted-data problems.