Problem 11.6 · Binary SearchMedium

Search a 2D Matrix

PatternBinary Search on an Index Matrix Traversal

What it teaches: Treat a row-sorted matrix as one virtual sorted array: index i maps to row i / cols, column i % cols.

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

The problem

Each row of an m × n matrix is sorted, and each row's first value is greater than the previous row's last value. Return whether target is present, in O(log(m·n)).

Example 1

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints

1 ≤ m, n ≤ 100

Pattern clues in the wording

→ Rows chain into one sorted sequence
→ Logarithmic time

These clues point to Binary Search on an Index: In sorted data, check the middle and throw away the half that can't contain the answer.

Stuck? Take one hint at a time

Solution.java · starter

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

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]] target = 3	true
2	matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]] target = 13	false

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: one virtual array · O(log(m·n))

Optimal: one virtual array

Time O(log(m·n)) Space O(1)

Search indexes 0 to m·n − 1; value at index i is matrix[i / n][i % n].

Approach 1

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int lo = 0, hi = m * n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int v = matrix[mid / n][mid % n];
            if (v == target) return true;
            if (v < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return false;
    }
}

Verdict: A single binary search.

Before you submit

Edge cases and common mistakes

Test these inputs

One row
One column
Target smaller than everything

Mistakes people make

Converting with mid / m instead of mid / n.

Interview

Follow-up questions

What if only rows and columns are sorted, but rows don't chain?

Command Palette

The problem

Approaches

Optimal: one virtual array

Edge cases and common mistakes

Follow-up questions