Topics › Binary Search › BS on 2D Arrays

Search in 2D matrix - II

Hard TUF ID 68 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an n × m integer matrix in which every row is sorted in increasing order from left to right and every column is sorted in increasing order from top to bottom. Nothing links the end of one row to the start of the next. Given a target, return true if it appears somewhere in the matrix and false otherwise.

Constraints: 1 ≤ n, m ≤ 300, values and target fit in a 32-bit signed integer.

Example 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
answer = true        // row 1, column 1

Example 2

same matrix, target = 20
answer = false       // 20 is bracketed by rows 1, 2, 3 and 4, but none of them holds it

Example 3

matrix = [[-5]], target = 5
answer = false

Compare with Search in a 2D matrix, where rows are chained so the matrix is one sorted list. Here 10 starts row 3 even though 15, 19, 22 appear in earlier rows, so the flatten-and-binary-search trick is invalid. We need an argument that uses both orderings at once.

Approach 1: Brute force, scan every cell

Intuition. Compare the target against every cell. This uses neither ordering and is the yardstick for the other approaches.

Algorithm.

1. For every row and every cell, return true on a match.
2. Return false otherwise.

static boolean bruteForce(int[][] matrix, int target) {
    for (int[] row : matrix) {
        for (int x : row) if (x == target) return true;
    }
    return false;
}

Complexity. Time O(n × m). Space O(1).

Approach 2: Better, binary search each candidate row

Intuition. Every row is sorted, so a binary search inside a row costs O(log m). Rows whose first element is above the target, or whose last element is below it, cannot contain it and can be skipped with two comparisons. Unlike the chained version, several rows may bracket the target, so we must keep going after a failed search instead of returning immediately.

Algorithm.

1. For each row: if row[0] <= target <= row[m − 1], binary search the row; return true on success.
2. Return false once all rows are tried.

static boolean inRow(int[] row, int target) {
    int lo = 0, hi = row.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (row[mid] == target) return true;
        if (row[mid] < target) lo = mid + 1; else hi = mid - 1;
    }
    return false;
}

static boolean better(int[][] matrix, int target) {
    for (int[] row : matrix) {
        if (row.length == 0) continue;
        if (row[0] <= target && target <= row[row.length - 1] && inRow(row, target)) return true;
    }
    return false;
}

Complexity. Time O(n log m) in the worst case, when many rows bracket the target. Space O(1).

This uses only the row ordering. The column ordering is sitting there unused, and exploiting it is what gets rid of the logarithm.

Approach 3: Optimal, the staircase walk from the top-right corner

Intuition. Stand on the top-right cell. It is the largest in its row and the smallest in its column. That makes it a perfect pivot:

• If it equals the target, done.
• If it is greater than the target, every cell below it in the same column is even greater, so the whole column can be discarded: move one step left.
• If it is smaller than the target, every cell to its left in the same row is even smaller, so the whole row can be discarded: move one step down.

After the move, the new cell is again the top-right cell of the remaining sub-matrix, so the same reasoning applies. Each step throws away an entire row or an entire column, and there are only n + m of those.

The top-left corner would not work: it is the smallest in both its row and its column, so a “greater than target” result tells us nothing about which direction to move. The bottom-left corner works symmetrically to the top-right one.

Algorithm.

1. Start at r = 0, c = m − 1.
2. While r < n and c >= 0: let value = matrix[r][c].
   • If value == target, return true.
   • If value > target, do c--.
   • Otherwise do r++.
3. Return false if the walk leaves the matrix.

static boolean optimal(int[][] matrix, int target) {
    int n = matrix.length;
    if (n == 0 || matrix[0].length == 0) return false;
    int m = matrix[0].length;
    int r = 0, c = m - 1;
    while (r < n && c >= 0) {
        int value = matrix[r][c];
        if (value == target) return true;
        if (value > target) c--;                 // everything below in this column is even larger
        else r++;                                // everything to the left in this row is even smaller
    }
    return false;
}

Dry run on Example 1 with target = 5:

And with target = 20:

The walk exits the matrix without a match, so the answer is false.

Complexity. Time O(n + m): r can increase at most n times and c can decrease at most m times. Space O(1).

Why can nothing be missed? Maintain the invariant “if the target is in the matrix, it is in the sub-matrix rows r..n−1, columns 0..c”. Initially that is the whole matrix. A step left discards column c, whose remaining cells (rows r..n−1) are all at least matrix[r][c] > target. A step down discards row r, whose remaining cells (columns 0..c) are all at most matrix[r][c] < target. Either way, the discarded cells cannot hold the target, so the invariant survives.

Edge cases and pitfalls

• Target bracketed by many rows. 20 in Example 1 lies within the ranges of rows 1 through 4. Approach 2 must not return false after the first failed row; the staircase handles it naturally.
• Target at the corners. The top-right 15 is found on the first step; the bottom-left 18 takes the longest walk (n + m − 1 steps). Both are in the test file.
• Smaller or larger than everything. 0 walks straight down the last column and exits; 31 walks straight left along the top row and exits. Both return false.
• Starting corner. Only the top-right and bottom-left corners work. Starting top-left or bottom-right gives no information about which way to go.
• Strict versus non-strict order. The walk is also correct when rows and columns are merely non-decreasing: discarded cells are then >= value > target or <= value < target, still never equal to the target.
• Empty matrix. Guard n == 0 before reading matrix[0].length.
• Mixing this up with the chained version. If you also know rows are chained, a single binary search on the flat index gives O(log(n × m)), which is faster than O(n + m). If you only know rows and columns are sorted, the staircase is the right tool; the flat search would be wrong.

Related problems

• Search in a 2D matrix adds the chained-rows guarantee and allows a single binary search over the flat index.
• Find row with maximum 1’s uses the same top-right staircase on a sorted binary matrix.
• Matrix Median counts elements below a value across sorted rows, a counting cousin of this search.
• Search X in sorted array is the one-dimensional binary search used inside Approach 2.