Search in a 2D Matrix
MediumFlatten to one sorted array
Treat the sorted grid as one long sorted list and do a normal halving search.
The idea
When each row starts after the previous row ends, the whole matrix is one sorted sequence. Binary search index i, mapping to (i / cols, i % cols).
1
3
5
7
10
11
16
20
23
30
34
60
target16
Step 1 of 8. Brute force: look at every cell until you find 16. target 16.
1/8
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 × 4
Memory
- at
- —
- cells marked
- 0
- target
- 16
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
- Output:
- true
- Explanation:
- 3 is in the first row.
Example 2
- Input:
- matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
- Output:
- false
- Explanation:
- 13 is nowhere → false.
Example 3
- Input:
- matrix = [[1]], target = 1
- 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.