Search a 2D Matrix II - Video Solutions

Problem Overview: You are given an m x n matrix where each row is sorted left to right and each column is sorted top to bottom. The task is to determine whether a target value exists in the matrix without scanning every element.

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

This approach exploits the sorted structure of both rows and columns. Start at the top-right element. From this position, each comparison eliminates either a full row or a full column. If the current value is greater than the target, move left because all values below are even larger. If the value is smaller than the target, move down since everything to the left is smaller. Each step removes one row or column from consideration, so you perform at most m + n moves.

The key insight: the top-right corner acts like a pivot where one direction strictly decreases and the other strictly increases. This allows deterministic movement similar to a two-pointer scan in a sorted grid. The algorithm uses only index movement and comparisons, so the extra memory remains constant. This technique frequently appears in problems involving sorted matrices and grid monotonicity, making it a useful pattern for array and matrix search problems.

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

Another option is to treat each row as an independent sorted array and apply binary search. Iterate through every row and check whether the target can exist in that row by comparing it with the row's first and last elements. If the target falls within that range, run binary search on that row to locate it.

This works because each row is individually sorted, which fits the classic binary search pattern. However, you still need to iterate through up to m rows, and each binary search costs O(log n). The result is O(m log n) time. While slower than the optimal solution, this approach is straightforward to implement and easy to reason about during interviews.

Recommended for interviews: Interviewers usually expect the top-right traversal. It shows you recognize the monotonic ordering across both dimensions and can eliminate rows or columns in constant time per step. The row-wise binary search approach demonstrates understanding of sorted arrays, but the O(m + n) strategy highlights stronger algorithmic insight and familiarity with matrix search patterns often discussed alongside divide and conquer style reasoning.