☕ DSA Java Articles

Topics › Binary Search › BS on 2D Arrays

Search in a 2D matrix

Hard TUF ID 69 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an n × m integer matrix with two properties: every row is sorted in non-decreasing order, and the first element of each row is strictly greater than the last element of the previous row. In other words, reading the matrix row by row gives one sorted sequence. Given a target, return true if it appears in the matrix and false otherwise.

Constraints: 1 ≤ n, m ≤ 100, values and target fit in a 32-bit signed integer. Aim for O(log(n × m)) time.

Example 1

matrix = [[ 1,  3,  5,  7],
          [10, 11, 16, 20],
          [23, 30, 34, 60]], target = 3
answer = true        // row 0, column 1

Example 2

same matrix, target = 13
answer = false       // 13 would fall between 7 and 10, in the gap between rows 0 and 1

Example 3

matrix = [[1]], target = 2
answer = false

The second property is what distinguishes this problem from Search in 2D matrix - II. Here rows do not merely happen to be sorted; the rows are chained, so the whole matrix is one sorted list that has been folded into rows of length m.

Approach 1: Brute force, scan every cell

Intuition. Ignore the ordering and compare every cell with the target. It is correct for any matrix and serves as the baseline the other approaches are checked against.

Algorithm.

  1. For each row and each cell in it, return true on a match.
  2. Return false if the loops finish.
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, locate the row then binary search it

Intuition. Because the rows are chained, the target can live in at most one row: the row whose first element is at most the target and whose last element is at least the target. Scan the rows to find it, then run an ordinary binary search inside that single row. If no row brackets the target, the target falls into a gap between rows (or outside the matrix entirely) and the answer is false.

Algorithm.

  1. For each row, test row[0] <= target <= row[m − 1].
  2. For the first (and only) row that passes, binary search it and return the result.
  3. If no row passes, return false.
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]) return inRow(row, target);
    }
    return false;
}

Complexity. Time O(n + log m): a linear scan over the rows plus one binary search. Space O(1).

Returning directly from inside the loop is valid only because rows are chained: once a row brackets the target, no other row can contain it. The row scan could itself be replaced by a binary search over first elements, giving O(log n + log m), which is the same as the next approach; the flat-index trick below achieves that with a single loop and no row bookkeeping.

Approach 3: Optimal, binary search on the flat index

Intuition. Imagine unrolling the matrix into a single sorted array of length n × m. We never need to build that array, because any flat index idx maps back to a cell by integer division and remainder: row = idx / m, col = idx % m. So a standard binary search over idx in [0, n × m − 1], reading matrix[idx / m][idx % m] wherever it would read arr[idx], searches the whole matrix in O(log(n × m)) time.

Algorithm.

  1. If the matrix has no rows or no columns, return false.
  2. Set lo = 0, hi = n × m − 1.
  3. While lo <= hi: compute mid and value = matrix[mid / m][mid % m].
    • If value == target, return true.
    • If value < target, set lo = mid + 1; otherwise hi = mid − 1.
  4. Return false.
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 lo = 0, hi = n * m - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int value = matrix[mid / m][mid % m];        // flat index -> (row, column)
        if (value == target) return true;
        if (value < target) lo = mid + 1; else hi = mid - 1;
    }
    return false;
}

Dry run on Example 1, target = 3, with n = 3, m = 4, so flat indices run from 0 to 11:

lo hi mid cell (mid / 4, mid % 4) value action
0 11 5 (1, 1) 11 11 > 3: hi = 4
0 4 2 (0, 2) 5 5 > 3: hi = 1
0 1 0 (0, 0) 1 1 < 3: lo = 1
1 1 1 (0, 1) 3 match: return true

Four probes instead of twelve cells.

Complexity. Time O(log(n × m)), which equals O(log n + log m). Space O(1).

Why is the mapping right? Row r occupies flat indices r × m through r × m + m − 1. For any idx in that range, idx / m is r (integer division drops the remainder) and idx % m is the offset within the row. Together with the chained-rows property, the flat sequence is sorted, so binary search is valid.

Edge cases and pitfalls