DSA problem

Search a 2D Matrix II

MediumBinary SearchPattern: Binary Searchtop600AmazonMicrosoftGoogleFacebook

Write an efficient algorithm that searches for a value target in an m × n integer matrix matrix. This matrix has the following properties: integers in each row are sorted in ascending order from left to right, and integers in each column are sorted in ascending order from top to bottom. Note: rows and columns are sorted independently — unlike in "Search a 2D Matrix", there is no global row-major ordering.

Without the strict row-major property, naive flattening fails. A row-by-row or column-by-column binary search costs O(m log n) or O(n log m), which is acceptable but not the cleanest. The textbook solution uses a single pointer that walks along an antidiagonal direction.

Start at the top-right corner (row = 0, col = n - 1). The element there is the largest in its row and the smallest in its column. So:

• If matrix[row][col] == target, return true.
• If matrix[row][col] > target, every element to its right (in the same column) is even larger and can be ruled out — move left (col--).
• If matrix[row][col] < target, every element above (in the same row, no — same column above) is smaller; actually every element above in the same column is smaller. Move down (row++) to look at larger values.

Each step eliminates an entire row or column. There are m + n rows and columns combined, so the search runs in O(m + n) time and O(1) space. This beats both naive O(m log n) row search and the simpler flattened approach (which is not even applicable here).

Examples

Constraints

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -10^9 <= matrix[i][j], target <= 10^9
• All the integers in each row and each column are sorted in ascending order.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

binary-searchmatrixdivide-and-conquer

Browse all DSA problems