Search a 2D Matrix

1. Problem & Core Objective

An m × n matrix where each row is sorted and each row's first value exceeds the previous row's last. Return whether target is present, in O(log(m·n)).

[[ 1, 3, 5, 7],
 [10,11,16,20],      target = 3   →  true
 [23,30,34,60]]      target = 13  →  false

Constraints: 1 <= m, n <= 100 · values in [-10^4, 10^4].

What's actually being tested: whether you read the second property. "Each row starts above the previous row's end" is what makes the whole grid one sorted sequence — and without it this is a harder, different problem.

2. First-Principles Thought Process

Row-sorted alone would leave you searching each row separately. The second property is the one that matters: concatenating the rows gives one ascending sequence.

So it's a plain binary search over [0, m·n − 1] — which is exactly the O(log(m·n)) the problem asks for, confirming the reading.

The only real work is converting a flat index back to a cell:

Divide by the column count — that's the stride, the number of cells in each row. Using rows is the standard slip, and §3 shows exactly where it lands instead.

3. Solution Paths

Approach 1 — Scan every cell (brute force)

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

Check every cell. Uses neither sortedness property.

• Time O(m · n) — 10,000 reads on a 100×100 matrix · Space O(1)

Counter-questions on this approach

⭐ "Both rows and the row-chaining are sorted, and you use neither. What's available?"

Together they make the matrix a single ascending sequence, so one comparison can discard half the entire grid — not one cell. That's O(m·n) → O(log(m·n)): about 14 comparisons instead of 10,000. And the problem states the logarithmic bound, so this violates the spec rather than merely underperforming.

"Could you improve it without changing the algorithm — just add early exits?"

Yes, and it's worth seeing why it isn't enough. Within a row you could break once v > target; across rows you could skip any row whose first element already exceeds the target. Both are real constant-factor wins, and on a lucky input you'd touch very few cells.

But the worst case is unchanged at O(m·n) — a target just below the last element still forces a full traversal. That's the tell that I'm optimizing at the wrong level: the structure supports something asymptotically better, and I should be exploiting it rather than trimming a linear scan.

"Is there a middle ground between this and full binary search?"

Yes — the staircase walk from the top-right corner, O(m + n). It only needs rows and columns individually sorted, not the row-chaining. It's the right answer for the weaker variant of this problem (§7), and it's a useful checkpoint: O(m·n) → O(m+n) → O(log(m·n)) as you exploit progressively more structure.

Each rung of that ladder reads less of the grid:

Approach 2 — Binary search per row

for (int[] row : matrix) {
    if (row[row.length - 1] >= target) {          // the only row that could contain it
        return Arrays.binarySearch(row, target) >= 0;
    }
}
return false;

How it works. Rows are increasing, so the first row whose last element reaches the target is the only row that could contain it.

Trace — find 3: row 0 ends at 7, and 7 >= 3, so row 0 is the candidate. Binary search [1,3,5,7] → found. Only one row was ever examined.

Trace — find 13: row 0 ends at 7 (too small, skip), row 1 ends at 20 and 20 >= 13, so search [10,11,16,20] → absent → false. Correctly stops without examining row 2.

• Time O(m + log n) — linear over rows, then one binary search · Space O(1)

Counter-questions on this approach

⭐ "The row-ending values are themselves sorted. Why scan them linearly?"

That's the inefficiency — I could binary search them too, making it O(log m + log n). Scanning leaves a whole logarithm on the table. At m ≤ 100 the difference is a handful of operations so this would pass, but it isn't the algorithm the stated bound asks for.

"Why return rather than continue once you find the candidate row?"

Because of the second property: if the target exists at all, it must be in the first row whose last element reaches it. Every earlier row ends below the target; every later row starts above this row's end. Exactly one candidate row, so there's no reason to keep looking.

Approach 3 — Treat it as one flat array (optimal)

public boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length, cols = matrix[0].length;
    int lo = 0, hi = rows * cols - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int val = matrix[mid / cols][mid % cols];       // flat index → cell

        if (val == target) return true;
        if (val < target) lo = mid + 1;
        else              hi = mid - 1;
    }
    return false;
}

Trace — find 3 (flat length 12):

• Time O(log(m·n)) — ~14 comparisons on 100×100 · Space O(1)

Counter-questions on this approach

⭐ "Why divide by cols rather than rows?"

cols is the number of cells in each row, so index / cols counts how many complete rows precede this cell. rows isn't the stride and is simply meaningless here.

The two divisors land on genuinely different cells:

On this 3×4 matrix the wrong version returns false for targets 7, 20 and 60 — a bug that passes every square test and fails a quarter of the real ones.

⭐ "Which property does this depend on, and what breaks without it?"

Entirely the second one — each row starting above the previous row's end. That's what makes the concatenation ascending. Without it (rows and columns each sorted, but rows not chained) the flat array isn't sorted and this is wrong. That variant needs a staircase walk from the top-right corner at O(m + n) — see §7.

"Could rows * cols overflow?"

Not at 100×100. For a matrix large enough that the cell count exceeds int, I'd widen the bounds and midpoint to long. Worth noting since the cell count is the search space here.

Approach 4 — Two binary searches

public boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length, cols = matrix[0].length;

    // 1. find the candidate row — HALF-OPEN bounds
    int lo = 0, hi = rows - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (matrix[mid][cols - 1] < target) lo = mid + 1;   // this row ends too low
        else                                hi = mid;       // could be this row
    }
    int row = lo;

    // 2. search within it — INCLUSIVE bounds
    int l = 0, r = cols - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (matrix[row][mid] == target) return true;
        if (matrix[row][mid] < target) l = mid + 1;
        else                           r = mid - 1;
    }
    return false;
}

Boundary-search the rows' last elements to find the candidate row, then search within it.

• Time O(log m + log n) = O(log(m·n)) — identical, since log m + log n = log(mn) · Space O(1)

Counter-questions on this approach

⭐ "Same complexity. Why prefer the flattened version?"

One search instead of two, and one bound convention instead of two — the row search wants half-open (lo < hi, hi = mid, because mid might be the answer row) while the column search wants inclusive. Mixing conventions inside one method is precisely where binary-search bugs come from. It's a readability argument, not a performance one.

"Why compare against matrix[mid][cols-1] rather than matrix[mid][0]?"

Because I want the first row whose last element reaches the target — that's the row whose range covers it. Comparing against a row's first element would find the last row starting below the target, which is off by one and needs a correction step. Comparing against the end gives the cleaner predicate.

"What if the target exceeds every element?"

The row search settles on the last row — lo can't exceed rows - 1 — and the column search then fails and returns false. No special case needed, but it's worth verifying, because a boundary search that can run past the end is a common source of exceptions.

4. Why the Optimal Wins

On 100×100: ~14 cell reads versus 10,000. The saving comes entirely from a property the problem hands you.

Against the two-stage version, the complexities are genuinely equal — the win is surface area for bugs: one loop, one convention, one comparison.

Why O(log(m·n)) is the floor: each comparison yields one bit, and distinguishing m·n positions needs log₂(m·n) bits.

The transferable idea:

A 2-D structure with a total ordering is a 1-D structure. Flatten the index rather than writing 2-D logic.

The same index / width conversion appears in Valid Sudoku's box indexing and in union-find over grids.

5. Java Prerequisites

Flat index conversion

int row = index / cols;          // divide by the COLUMN count — cells per row is the stride
int col = index % cols;
int index = row * cols + col;    // and back again

The inverse direction is what you use to turn a grid coordinate into a single integer key — for union-find over grids (17) or for a HashSet of visited cells.

Matrix dimensions

int rows = matrix.length;        // number of rows
int cols = matrix[0].length;     // columns — guard rows > 0 first

A Java 2-D array is an array of arrays, so rows are independent objects and could have different lengths (a "jagged" array). The constraints here guarantee rectangular; with a jagged matrix the flat-index arithmetic breaks entirely.

Arrays.binarySearch on a single row

Arrays.binarySearch(row, target) >= 0     // found
// absent → -(insertionPoint) - 1, always negative

The >= 0 test is the idiomatic "was it found". Don't use it when duplicates matter — no promise about which matching index you get. See 10.

Overflow

int hi = rows * cols - 1;
int mid = lo + (hi - lo) / 2;

At 100×100 the product is 10,000 — no risk. For a matrix whose cell count exceeds int, widen both to long. The cell count being the search space is exactly why that multiplication matters here.

6. Interview Communication Guide

Clarifying questions: Does each row start above the previous row's end (the key question)? Rectangular or jagged? Return boolean or position?

The pitch

"The important detail is the second property — each row's first element exceeds the previous row's last. That means concatenating the rows gives one ascending sequence. For search purposes this isn't a grid; it's a sorted array of m·n elements that happens to be stored in rows.

So I binary search the flat range [0, m·n − 1], converting each midpoint back with row = mid / cols, col = mid % cols. I divide by the column count because that's the stride — cells per row.

O(log(m·n)), matching the requirement: about 14 comparisons on 100×100 versus 10,000 for a scan.

There's an equivalent two-stage version — find the row, then search it — at the same complexity, since log m + log n = log(m·n). I prefer the flattened one because it's a single search with a single bound convention.

One thing I'd flag: dividing by rows instead of cols gives correct output on square matrices, so it's a bug that survives casual testing."

Edge cases to volunteer:

The degenerate shapes are the ones to name — they're where the index arithmetic collapses, and the cheapest check that cols is the right divisor.

7. Follow-Up Questions — Modified Constraints

⭐ "Rows and columns each sorted, but rows don't chain." (LC 240)

Flattening breaks — the concatenation is no longer ascending. Use a staircase walk from the top-right: too big → move left (everything below in that column is larger); too small → move down (everything left in that row is smaller). Each step eliminates a full row or column: O(m + n). Note that's worse than O(log(m·n)), necessarily — the weaker ordering carries less information.

"Return the position rather than a boolean."

new int[]{mid / cols, mid % cols} — the decomposition is already computed.

"The matrix is too large to hold in memory."

Binary search never materializes the structure; it needs only O(1) random access to individual cells. It works directly against a disk-backed or remote matrix with ~40 cell reads for a billion cells — the same access pattern as a B-tree index lookup.

"Duplicates, and you need the first occurrence."

lowerBound over the flat index with value >= target, then verify. Still O(log(m·n)) — a one-line change in the flat framing, which is another argument for it over the two-stage version.