Search a 2D Matrix - Video Solutions

Problem Overview: 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. The task is to determine whether a given target value exists in the matrix.

Approach 1: Binary Search on Matrix as a 1D Array (O(log(m*n)) time, O(1) space)

The key insight is that the matrix behaves like a globally sorted array. Because every row starts with a value greater than the previous row’s last value, you can conceptually flatten the matrix into a single sorted list of size m * n. Run standard binary search on indices from 0 to m*n - 1. Convert a 1D index back to matrix coordinates using row = mid / n and col = mid % n. Each step compares matrix[row][col] with the target and halves the search space. This approach is optimal because it treats the structure as a single sorted dataset while keeping constant memory.

Approach 2: Two-step Binary Search (Row then Column) (O(log m + log n) time, O(1) space)

This method performs two separate binary searches. First, run binary search on the rows to locate the only row that could contain the target. Compare the target with the first and last element of each row to narrow down the candidate row. Once the correct row is identified, run a second binary search within that row to locate the target value. This approach explicitly uses the row ordering property of the matrix and the sorted order inside each row. It is easy to reason about during interviews because the two steps clearly mirror the structure of the data.

Both solutions rely on the same property: the matrix behaves like a sorted structure. The first approach compresses the entire matrix into a conceptual array, while the second approach searches rows and columns separately. Either way, the algorithm repeatedly halves the search space using array indexing and binary search comparisons.

Recommended for interviews: The 1D binary search approach is usually the expected optimal solution. It demonstrates that you recognize the matrix is globally sorted and can transform the problem into classic binary search. The two-step method is also accepted and often easier to derive during an interview because it directly uses the matrix layout.