29.Search a 2D Matrix

MediumBinary Search · 2/7

Problem

You are given an m x n integer matrix with two properties:

Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in the matrix and false otherwise. The solution must run in O(log(m · n)) time.

Examples

Input:  matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Explanation: 3 is in row 0, column 1.

Input:  matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Explanation: 13 would belong in row 1 between 11 and 16, but it is not there.

Constraints

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4

💡 Key Insight

The two properties together mean that reading the matrix row by row produces one fully sorted list of m · n numbers. So we can binary-search a "virtual" 1-D array of length m · n, translating a 1-D index k into the cell matrix[k / n][k % n]. No copying is needed.

Brute Force

TimeO(m · n)SpaceO(1).

Intuition

Scan every cell and compare it to target.

Algorithm

For every row r and column c, if matrix[r][c] == target return true.
Return false.

Visualization

target = 3
row 0: 1 ✗  3 ✓ → return true

Code

java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            for (int value : row) {
                if (value == target) {
                    return true;
                }
            }
        }
        return false;
    }
}

Complexity

Time: O(m · n) — every cell may be visited.
Space: O(1).

Staircase Search from Top-Right

TimeO(m + n)SpaceO(1).

Intuition

Start at the top-right corner. Every value to its left is smaller and every value below is larger. So if the current value is too big, the whole column can be dropped (move left); if it is too small, the whole row can be dropped (move down). Each step eliminates a row or a column.

Algorithm

Set r = 0, c = n - 1.
While r < m and c >= 0:
- If matrix[r][c] == target return true.
- If matrix[r][c] > target, c--; else r++.
Return false.

Dry Run

target = 13
(0,3)=7  < 13 → down
(1,3)=20 > 13 → left
(1,2)=16 > 13 → left
(1,1)=11 < 13 → down
(2,1)=30 > 13 → left
(2,0)=23 > 13 → left → c = -1, stop → false

Code

java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int r = 0;
        int c = matrix[0].length - 1; // start at top-right corner
        while (r < rows && c >= 0) {
            int value = matrix[r][c];
            if (value == target) {
                return true;
            } else if (value > target) {
                c--; // everything below in this column is even larger
            } else {
                r++; // everything left in this row is even smaller
            }
        }
        return false;
    }
}

Complexity

Time: O(m + n) — each step removes one row or one column.
Space: O(1).

Two Binary Searches

TimeO(log m + log n) = O(log(m · n)).SpaceO(1).

Intuition

First binary-search over the rows to find the one row whose range [row[0], row[n-1]] could contain target. Then binary-search inside that row.

Algorithm

Binary search rows with top = 0, bot = m - 1:
- If target > matrix[mid][n-1], go down (top = mid + 1).
- Else if target < matrix[mid][0], go up (bot = mid - 1).
- Else this row is the candidate; stop.
If no row was found, return false.
Standard binary search for target in that row.

Dry Run

target = 3
rows: top=0, bot=2 → mid=1, row 1 = [10..20], 3 < 10 → bot=0
      top=0, bot=0 → mid=0, row 0 = [1..7], 1 ≤ 3 ≤ 7 → candidate row 0
row 0: lo=0, hi=3 → mid=1, value 3 == 3 → true

Code

java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;

        // 1) find the row whose range can contain target
        int top = 0, bot = m - 1, row = -1;
        while (top <= bot) {
            int mid = top + (bot - top) / 2;
            if (target > matrix[mid][n - 1]) {
                top = mid + 1;
            } else if (target < matrix[mid][0]) {
                bot = mid - 1;
            } else {
                row = mid;
                break;
            }
        }
        if (row == -1) {
            return false;
        }

        // 2) binary search inside that row
        int lo = 0, hi = n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (matrix[row][mid] == target) {
                return true;
            } else if (matrix[row][mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return false;
    }
}

Complexity

Time: O(log m + log n) = O(log(m · n)).
Space: O(1).

Single Binary Search on Flattened IndexOptimal

TimeO(log(m · n))SpaceO(1).

Intuition

Treat the matrix as a sorted 1-D array of length m · n. Index k maps to row k / n and column k % n. Run one ordinary binary search over [0, m·n - 1].

Algorithm

lo = 0, hi = m * n - 1.
While lo <= hi:
- mid = lo + (hi - lo) / 2, value = matrix[mid / n][mid % n].
- If value == target return true; if value < target set lo = mid + 1; else hi = mid - 1.
Return false.

Dry Run

flowchart TD
    A["m=3, n=4, target=13<br/>lo=0, hi=11"] --> B["mid=5 → (1,1) = 11"]
    B -->|"11 < 13"| C["lo=6, hi=11"]
    C --> D["mid=8 → (2,0) = 23"]
    D -->|"23 > 13"| E["lo=6, hi=7"]
    E --> F["mid=6 → (1,2) = 16"]
    F -->|"16 > 13"| G["lo=6, hi=5"]
    G --> H["range empty → return false"]

Code

java

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

Complexity

Time: O(log(m · n)) — one binary search over all cells.
Space: O(1).

Complexity Comparison

Approach	Time	Space
Brute Force	O(m · n)	O(1)
Staircase Search	O(m + n)	O(1)
Two Binary Searches	O(log m + log n)	O(1)
Flattened Binary Search	O(log(m · n))	O(1)

Common Pitfalls

Mapping the index with the wrong dimension: it is mid / n and mid % n where n is the number of columns, not rows.
In the two-step approach, binary-searching only on row[0] and then picking the wrong row when target is smaller than every first element — check for "no row found".
Using the staircase method and claiming O(log) time — it is O(m + n); it is the right tool for LeetCode 240 (Search a 2D Matrix II) where rows do not chain together.
Forgetting the single-row / single-column case (m = 1 or n = 1) — the flattened search handles both naturally.