Search a 2D Matrix II

Problem Statement

Search for target in an m x n integer matrix where:

• Each row is sorted in ascending order (left to right).
• Each column is sorted in ascending order (top to bottom).

Return true if target exists, else false.

Example 1:

Input: 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
Output: true

Example 2:

Input: matrix = [[1,2,3], [4,5,6], [7,8,9]], target = 10
Output: false

Constraints:

• 1 <= m, n <= 300.
• -10^9 <= matrix[i][j] <= 10^9.
• -10^9 <= target <= 10^9.

Difficulty: Medium LC: 240 Round: Technical R1

---

Pattern Recognition

• What is the input structure? A 2D matrix sorted row-wise and column-wise (but NOT a flat sorted 1D array when read in row-major order).
• What are we optimizing? Find target in sublinear time per dimension.
• What pattern does this fit? Staircase search from a "pivot" corner.
• Why does this pattern fit? From the top-right corner, every cell to the left is smaller and every cell below is larger. This gives a binary-search-like elimination at each step.

LC 74 (the "flat 1D sorted" variant) can be solved with a single binary search. LC 240 cannot — adjacent rows can overlap.

---

Approach

Brute Force — Scan Every Cell

Linear scan over all m * n cells.

Time: O(m * n). Space: O(1). Why insufficient: Doesn't exploit the sort. For large matrices, unacceptable.

Suboptimal — Binary Search Each Row

Run binary search on each row.

Time: O(m log n). Space: O(1). Why this isn't optimal: Doesn't use column sort. O(m + n) exists.

Optimal — Staircase from Top-Right

Key Insight: At the top-right corner, the current cell is the maximum of its row and the minimum of its column. Compare with target:

• If current == target, done.
• If current < target, the entire current row (to the left) is too small, so move down.
• If current > target, the entire current column (below) is too large, so move left.

Each step eliminates a full row or a full column.

Step-by-step:

1. Set r = 0, c = n - 1.
2. While r < m and c >= 0:
   • If matrix[r][c] == target, return true.
   • Else if matrix[r][c] < target, r++.
   • Else c--.
3. Return false.

Time: O(m + n) — at most m + n moves. Space: O(1).

---

Walkthrough

Trace on the 5x5 matrix above, target = 5:

Start at r=0, c=4: matrix[0][4] = 15.

step	r	c	matrix[r][c]	compare to 5	action
1	0	4	15	> 5	c--
2	0	3	11	> 5	c--
3	0	2	7	> 5	c--
4	0	1	4	< 5	r++
5	1	1	5	==	return true

Answer: true.

Trace on target = 10 (not in the matrix):

step	r	c	value	action
1	0	4	15	> → c--
2	0	3	11	> → c--
3	0	2	7	< → r++
4	1	2	8	< → r++
5	2	2	9	< → r++
6	3	2	14	> → c--
7	3	1	13	> → c--
8	3	0	10	==

Wait — 10 is in the matrix. Let me retry with a value clearly absent: target = 20.

step	r	c	value	action
1	0	4	15	< → r++
2	1	4	19	< → r++
3	2	4	22	> → c--
4	2	3	16	< → r++
5	3	3	17	< → r++
6	4	3	26	> → c--
7	4	2	23	> → c--
8	4	1	21	> → c--
9	4	0	18	< → r++
10	5	0	out of bounds	return false

Answer: false.

---

Implementation

TypeScript

function searchMatrix(matrix: number[][], target: number): boolean {
    if (matrix.length === 0 || matrix[0].length === 0) return false;
    const m = matrix.length, n = matrix[0].length;

    // Start at top-right: current cell is max of row, min of column.
    let r = 0, c = n - 1;
    while (r < m && c >= 0) {
        if (matrix[r][c] === target) return true;
        if (matrix[r][c] < target) r++;
        else c--;
    }
    return false;
}

C++

#include <vector>

bool searchMatrix(std::vector<std::vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty()) return false;
    int m = matrix.size(), n = matrix[0].size();
    int r = 0, c = n - 1;
    while (r < m && c >= 0) {
        if (matrix[r][c] == target) return true;
        if (matrix[r][c] < target) r++;
        else c--;
    }
    return false;
}

Watch out:

1. Starting at top-left or bottom-right. These corners fail — the comparison doesn't eliminate anything usefully (both "bigger" and "smaller" directions are meaningful).
2. Per-row binary search. O(m log n) — worse than O(m + n) for small n.
3. Out-of-bounds access. Check r < m and c >= 0 each iteration.

---

Complexity Analysis

	Time	Space
Brute Force	O(m * n)	O(1)
Binary Search Per Row	O(m log n)	O(1)
Staircase (Optimal)	O(m + n)	O(1)

Bottleneck: Each step moves down or left exactly once; total moves bounded by m + n.

---

Edge Cases

1. Empty matrix — return false.
2. Target smaller than matrix[0][0] — first comparison is >, c decrements past 0; return false.
3. Target larger than matrix[m-1][n-1] — r increments past m-1; return false.
4. Single row or single column — reduces to 1D binary search; the algorithm still works.
5. Duplicates — the algorithm stops at the first match.

---

Related Problems

• LC 74 — Search a 2D Matrix — Simpler variant where the matrix is effectively a flat sorted array in row-major order. One binary search.
• LC 378 — Kth Smallest Element in a Sorted Matrix — Different problem, same matrix structure.
• LC 668 — Kth Smallest Number in Multiplication Table — Binary search on answer + staircase counting.

---

Interview Strategy Notes

Classic Technical R1 warmup. 10-15 minutes. The interviewer may push on "why start at top-right?" — be ready to explain that only corners where one direction strictly increases and the other strictly decreases work. Bottom-left works symmetrically.

---

What is Expected at Each Level

Junior: Offers binary-search-per-row, then with a hint about "staircase" writes the optimal.

Mid-level: Goes to staircase directly, explains why top-right works. Discusses bottom-left as an equivalent starting corner.

Senior: Proves the O(m + n) bound. Explains why this matrix structure does not permit O(log(m + n)) — the diagonals are not sorted, so you can't binary-search across them. Mentions divide-and-conquer as a theoretically interesting O(n log n) on square matrices but notes staircase is practically superior.