Search a 2D Matrix II

medium

Search for a target in a sorted matrix where each row and each column is sorted ascending

Search a 2D Matrix II

Key Insight

Start top-right and eliminate one row/column per comparison.

Step 1Start at Top-Right
Target=5
1
0
4
1
7
2
11
3
15
4
2
5
5
6
8
7
12
8
19
9
3
10
6
11
9
12
16
13
22
14
10
15
13
16
14
17
17
18
24
19
18
20
21
21
23
22
26
23
30
24

Move from (0,4) in a matrix sorted by rows and columns.

1 / 3

Learn the Pattern

Binary SearchEliminate half the search space each iteration by comparing the midpoint against a condition, reducing O(n) linear scans to O(log n).
Practice the Code

Step-by-Step Walkthrough: Search a 2D Matrix II

Start top-right and eliminate one row/column per comparison.

  1. Start at Top-Right

    Move from (0,4) in a matrix sorted by rows and columns.

  2. Move Left

    15 > 5 so eliminate first row by moving left.

  3. Move Down

    11 > 5, move left again to 7. then 7 > 5, move down to 3rd row? continue until target found.