Search a 2D Matrix II — Google Staircase Search Interview Question

Problem Statement#

Given an m by n matrix where each row is sorted left to right and each column is sorted top to bottom, return whether a target value exists.

Constraints:

• 1 <= m, n <= 300
• Values in the matrix and target fit in 32-bit signed int
• Rows are independently sorted, columns are independently sorted
• The matrix is not guaranteed to be globally sorted as a flat array

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

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

Why This Problem Matters#

This is LeetCode 240 Search a 2D Matrix II and it sits in Google's most asked top fifty for phone screens. Google interviewers like it because the obvious O(m times n) scan is too slow for the upper bounds and a row-by-row binary search at O(m log n) feels clever but still loses to the optimal O(m + n) staircase walk. The problem rewards candidates who notice the row-and-column sort invariant rather than treating the matrix as a flat sorted array.

The Core Insight#

Start at the top-right corner. The cell at matrix[r][c] is the largest value in its row to its left and the smallest value in its column below. So a single comparison eliminates a whole row or a whole column at each step.

If matrix[r][c] equals target, return true. If it is greater than target, the entire column below is also greater so move left. If it is less than target, the entire row to the left is also less so move down.

You start with m + n choices to make and each step uses one of them, so the total work is bounded by m + n comparisons.

Visual Dry Run#

Solution (Optimal)#

class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix or not matrix[0]:
            return False
        m, n = len(matrix), len(matrix[0])
        r, c = 0, n - 1
        while r < m and c >= 0:
            if matrix[r][c] == target:
                return True
            if matrix[r][c] > target:
                c -= 1
            else:
                r += 1
        return False

var searchMatrix = function(matrix, target) {
    if (!matrix.length || !matrix[0].length) return false;
    let r = 0, c = matrix[0].length - 1;
    while (r < matrix.length && c >= 0) {
        if (matrix[r][c] === target) return true;
        if (matrix[r][c] > target) c--;
        else r++;
    }
    return false;
};

Time: O(m + n) — every step eliminates one row or one column Space: O(1) — only the two pointers r and c

Common Mistakes#

• Starting from the top-left corner where both directions move toward larger values, blocking elimination
• Trying a global binary search by treating the matrix as flat — it is not
• Forgetting to bounds-check c >= 0 and r < m together, causing index errors
• Using row-by-row binary search and stopping at O(m log n) without recognising the better corner walk
• Returning the indices instead of the boolean when the prompt asks for boolean

Interview Tips#

• Verbalise that the naive scan is O(m times n) and exists, then propose the staircase walk
• Draw the matrix and mark the top-right pointer before coding
• Explain why top-right and bottom-left are the only valid starting corners
• Mention the two-corner symmetry — bottom-left works with r-- and c++
• If asked, extend to return the position by storing [r, c] instead of true

Follow-up Questions#

• Return all positions of the target, not just one. (Hint: continue the walk after a hit)
• Count values strictly less than target. (Hint: track number of cells to the upper-left of the staircase)
• What if rows and columns are sorted but the matrix is huge and only on disk? (Hint: same walk, only O(m + n) reads)
• Solve LeetCode 74 — fully sorted row-major matrix. (Hint: single binary search on the flattened index)
• Apply staircase logic to a 3D sorted cube. (Hint: pick a corner, eliminate a face per step)

Key Takeaways#

• LeetCode 240 is a Google top fifty problem solvable in O(m + n)
• The top-right or bottom-left corner is what unlocks the staircase elimination
• Each comparison removes a full row or full column from consideration
• O(m log n) row-by-row binary search is correct but suboptimal
• The pattern generalises to higher dimensions and to streaming or disk-backed data
• Space stays O(1) — no extra structures, just two pointers
• Watch the bounds — the loop ends when r reaches m or c falls below zero