Search a 2D Matrix II - Video Solutions

Problem Overview: You are given an m x n matrix where every row is sorted left to right and every column is sorted top to bottom. The task is to determine whether a target value exists in the matrix. The challenge is using the sorted structure efficiently instead of scanning every cell.

Approach 1: Start from Top-Right Corner (O(m + n) time, O(1) space)

This approach exploits the matrix ordering by starting from the top-right cell. From this position, you can eliminate either an entire row or an entire column in a single step. If the current value is greater than the target, move left to reduce the value. If it is smaller, move down to increase it. Because each move discards either one row or one column, the search path forms a monotonic staircase and never revisits cells. In the worst case you move at most m steps downward and n steps left, resulting in O(m + n) time with O(1) extra space. This technique is common when working with sorted matrix structures and leverages properties similar to two-pointer elimination strategies in array problems.

Approach 2: Binary Search in Rows (O(m log n) time, O(1) space)

Another strategy is to treat each row as a sorted array and run binary search on rows that could contain the target. For every row, first check whether the target lies between the first and last element of that row. If it does, perform binary search within that row. Each search costs O(log n), and doing this across m rows results in O(m log n) time. The space usage remains O(1) since the search happens in place. This method is straightforward if you already recognize the pattern of applying binary search on sorted ranges, though it does not exploit the column ordering as effectively as the top-right traversal.

Recommended for interviews: The top-right corner traversal is the expected solution in most interviews. It demonstrates that you recognize how both row-wise and column-wise ordering interact. Implementing the binary search per row shows baseline understanding of sorted arrays, but the O(m + n) elimination strategy signals stronger algorithmic insight and usually becomes the discussion point during interviews.