AlgoViz
HomeBinary Search

Search in 2D matrix - II

Hard

Start at a corner where one move goes each way

Problem

Given a 2D matrix where each row is sorted left-to-right and each column is sorted top-to-bottom, search efficiently for a target value.

In simple words

Start at the top-right corner: go left if the cell is too big, down if too small — a staircase walk.

The idea

From the top-right corner, moving left strictly decreases the value and moving down strictly increases it. That gives a decision at every step with no backtracking, eliminating a whole row or column each time in O(rows + cols).

The trick

  • Top-right or bottom-left — the other two corners give no useful comparison.
  • Larger than the target: move left. Smaller: move down.
  • The rows are not globally sorted, so a single binary search over all cells is wrong here.
1
4
7
2
5
8
3
6
9
target5

Step 1 of 6. Brute force: look at every cell until you find 5. target 5.

1/6
Brute force
timeO(m·n)spaceO(1)

Scan every cell.

1for (let r = 0; r < R; r++)2  for (let c = 0; c < C; c++)3    if (mat[r][c] === target) return true;

Input

grid
3 × 3

Memory

at
—
cells marked
0
target
5

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
matrix = [[1,4,7],[2,5,8],[3,6,9]], target = 5
Output:
true
Explanation:
5 sits in the middle.

Example 2

Input:
matrix = [[1,4,7],[2,5,8],[3,6,9]], target = 0
Output:
false
Explanation:
0 is below the smallest → false.

Example 3

Input:
matrix = [[5]], target = 5
Output:
true
Explanation:
Single cell match.

Constraints

  • 1 <= n, m <= 300
  • -10^9 <= matrix[i][j], target <= 10^9
  • Rows and columns are sorted ascending.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.