Search a 2D Matrix II — Staircase Search O(m+n) [LC 240]

Problem Statement#

Given an m x n integer matrix where each row is sorted left to right and each column is sorted top to bottom, return true if target exists in the matrix, or false otherwise.

Constraints:

• m == matrix.length, n == matrix[i].length
• 1 <= m, n <= 300
• -10^9 <= matrix[i][j] <= 10^9
• All integers in each row are sorted in ascending order
• All integers in each column are sorted in ascending order
• -10^9 <= target <= 10^9

Example 1:

Input: matrix = [[1,4,7,11],
                 [2,5,8,12],
                 [3,6,9,16],
                 [10,13,14,17]], target = 5
Output: true

Example 2:

Input: matrix = [[1,4,7,11],
                 [2,5,8,12],
                 [3,6,9,16],
                 [10,13,14,17]], target = 20
Output: false

Example 3:

Input: matrix = [[1,2],[3,4]], target = 3
Output: true

Why This Problem Matters#

LC 240 is a classic FAANG interview staple asked by Google, Amazon, and Meta. It tests whether you understand when binary search applies and when it does not. The matrix is sorted in two independent directions — rows and columns — but not globally (unlike LC 74 Search a 2D Matrix where values increase row by row). That subtle difference kills the simple binary search approach.

The staircase technique you learn here generalises to a wide class of elimination problems: any 2D structure where each position has a definitive left/right or up/down monotonicity. It also underpins the O(m+n) approach for counting negatives (LC 1351) and appears as a sub-routine in constructing Young tableaux.

Interviewers use this problem to see whether candidates reflexively reach for binary search, or whether they reason about the elimination property from first principles. The correct O(m+n) solution requires a key insight that many engineers miss on first attempt.

The Core Insight#

Neither the top-left corner nor any interior cell is a good starting position. From the top-left, both right and down increase — you can never eliminate a direction. From an interior cell, all four directions are possible.

The top-right corner (or equivalently the bottom-left corner) is special:

• Moving left decreases the value.
• Moving down increases the value.

So at each step you compare matrix[r][c] against target:

1. If they are equal — found it.
2. If matrix[r][c] > target — the entire column c from row r downward is too large. Eliminate column c by moving left (c -= 1).
3. If matrix[r][c] < target — the entire row r from column c leftward is too small. Eliminate row r by moving down (r += 1).

Each comparison eliminates a full row or a full column. The search terminates in at most m + n steps.

Visual Dry Run#

Matrix:

 1   4   7  11
 2   5   8  12
 3   6   9  16
10  13  14  17

Target = 5, start at top-right (r=0, c=3) → value 11.

Target = 20, start at (r=0, c=3).

Common Mistakes#

1. Applying binary search per row independently. Each row is sorted, so binary search per row gives O(m log n). This is worse than the O(m+n) staircase — and the matrix's column ordering is left completely unused.

2. Starting from the top-left corner. At (0,0), both right and down increase. You can never eliminate a direction, so the algorithm has no way to make a decision.

3. Confusing this problem with LC 74. LC 74 has a globally sorted matrix that you can flatten and binary search in O(log(mn)). LC 240 is only row-and-column sorted — the globally sorted property does not hold.

4. Off-by-one in bounds check. The loop condition must be r < m and c >= 0. Using <= or >= 1 introduces subtle out-of-bounds errors.

5. Forgetting the column boundary when moving left. After c reaches -1, the loop must terminate. Omitting the c >= 0 guard causes an index error.

6. Incorrect direction of movement. If matrix[r][c] > target, you move left (not up). Moving up would lose part of the row that might still contain the target.

Solutions#

Python#

def searchMatrix(matrix: list[list[int]], target: int) -> bool:
    # Edge case: empty matrix
    if not matrix or not matrix[0]:
        return False
 
    m, n = len(matrix), len(matrix[0])
 
    # Start at top-right corner — unique elimination point
    r, c = 0, n - 1
 
    while r < m and c >= 0:                  # stay within bounds
        val = matrix[r][c]
 
        if val == target:                     # found the target
            return True
        elif val > target:                    # current column too large — eliminate column
            c -= 1                            # move left
        else:                                 # current row too small — eliminate row
            r += 1                            # move down
 
    return False                              # exhausted search space without finding target

JavaScript#

function searchMatrix(matrix, target) {
    // Edge case: empty matrix
    if (!matrix.length || !matrix[0].length) return false;
 
    const m = matrix.length;
    const n = matrix[0].length;
 
    // Start at top-right corner
    let r = 0;
    let c = n - 1;
 
    while (r < m && c >= 0) {               // stay within bounds
        const val = matrix[r][c];
 
        if (val === target) {                // found the target
            return true;
        } else if (val > target) {           // column too large — move left
            c--;
        } else {                             // row too small — move down
            r++;
        }
    }
 
    return false;                            // target not present
}

Complexity Analysis#

The staircase is optimal. Any algorithm must inspect at least m + n - 1 positions in the worst case, so O(m+n) is tight.

Follow-up Questions#

1. What if you need to find the position (row, col) of the target? Return (r, c) at the equality check instead of True.
2. What if the matrix is sorted bottom to top / right to left? Start from the bottom-left corner and reverse the elimination directions.
3. Can you count occurrences instead of checking existence? No — the element may appear at most once by the problem's constraints. But for a variant with duplicates, you'd need a different strategy.
4. LC 74 vs LC 240 — Can you always distinguish them at a glance and choose the right algorithm in an interview?

This Pattern Solves#

• LC 240 — Search a 2D Matrix II (this problem)
• LC 1351 — Count Negative Numbers in a Sorted Matrix
• LC 74 — Search a 2D Matrix (simpler variant — use binary search directly)
• Any 2D structure with independent row/column monotonicity where corner elimination applies

Key Takeaway#

The top-right corner of a row-and-column sorted matrix is the unique position with one monotone direction in each axis — making it the only valid elimination starting point. Starting there reduces a 2D search to a 1D zigzag walk costing O(m+n). If you reflexively reach for binary search on a sorted 2D matrix, pause and ask whether the matrix is globally sorted or only row-and-column sorted — the answer determines which algorithm to use.

Key Takeaways#

• LC 240 is asked by Google, Amazon, and Meta to test whether candidates distinguish globally sorted matrices (LC 74) from row-and-column sorted matrices (this problem).
• The top-right corner is the unique starting position where one direction always increases and the other always decreases, enabling a definitive elimination at every step.
• From top-right: if matrix[r][c] > target, eliminate the entire column by moving left (c--); if matrix[r][c] < target, eliminate the entire row by moving down (r++).
• The algorithm runs in O(m + n) — each step eliminates one full row or column, and there are at most m + n - 1 steps total.
• Starting from the top-left or any interior cell is wrong — the top-left has both directions increasing, making elimination impossible.
• Flat-index binary search from LC 74 does NOT work here — the matrix is not globally sorted, so the flat sequence is not monotone.
• This staircase technique also solves LC 1351 (Count Negatives in Sorted Matrix) in O(m + n) instead of the naive O(m log n).