Command Palette

Search for a command to run...

Hectal
Problem 38.2 · Advanced Search and Divide & ConquerMedium

Search a 2D Matrix II

PatternDivide and ConquerTwo Pointers: Opposite Ends

What it teaches: Start at a corner where one move increases and the other decreases: each step discards a whole row or column.

Practise it on judges as “Search a 2D Matrix II”.

In plain words

Picture a table of numbers that grow as you go right and as you go down. Stand in the top-right corner: everything to your left is smaller and everything below is bigger. If your number is too big, step left; if too small, step down. Every step rules out a whole column or a whole row.

Return true if the target is in the table. Example: the 5 × 5 example with target = 5 → true.

The problem

Rows are sorted left to right and columns top to bottom. Return true if target is in the matrix.

Example 1

Input: matrix = 5 × 5 example, target = 5
Output: true

Constraints

  • 1 ≤ m, n ≤ 300

Pattern clues in the wording

  • → Rows and columns both sorted

These clues point to Divide and Conquer: Split the input into halves, solve each half recursively, and combine the results.

Stuck? Take one hint at a time

Solution · starter
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        return false;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#InputExpected
1
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
target = 5
true
2
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
target = 20
false

From slow to fast

Approaches

1. Staircase from the top-right · O(m + n)
1

Staircase from the top-right

Time O(m + n) Space O(1)

If the value is larger than target, discard the column (move left); if smaller, discard the row (move down).

▶ Dry run: Staircase walk from the top-rightmatrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
1
4
7
11
15
2
5
8
12
19
3
6
9
16
22
10
13
14
17
24
18
21
23
26
30

Step 1/5Start at the top-right: 15. It is bigger than 5, so the whole last column (15 and below) is too big. Step left.

Approach 1
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int r = 0, c = matrix[0].length - 1;
        while (r < matrix.length && c >= 0) {
            int v = matrix[r][c];
            if (v == target) return true;
            if (v > target) c--; else r++;
        }
        return false;
    }
}

Verdict: Simpler and faster than recursive quadrant splitting.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Target smaller than everything
  • Single cell

Mistakes people make

  • Starting at the top-left (both moves increase, so nothing can be discarded).

Interview

Follow-up questions

What's the divide-and-conquer version?