Search in a 2D Matrix II
MediumStaircase from the top-right
Start at the top-right corner; go left if the number is too big, down if it's too small.
The idea
Rows and columns are each sorted. Start at the top-right corner: a value too big means move left, too small means move down — one wrong direction is eliminated each step.
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.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.