Search a 2D Matrix II: The Staircase Search

Search a 2D Matrix II is LeetCode 240, and it looks deceptively similar to its predecessor, Search a 2D Matrix. But there is a critical difference. In this version, each row is sorted and each column is sorted, but the first element of one row is not necessarily greater than the last element of the previous row. That means you cannot flatten the matrix into a single sorted array. You need a different strategy.

The problem

You are given an m x n integer matrix where:

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

Given an integer target, return true if the target exists in the matrix, or false otherwise.

Example: 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. The answer is true.

Notice the structure. Every value is larger than everything above it in its column and larger than everything to its left in its row. This double-sorted property is the key to the entire solution.

Why binary search per row is not good enough

Your first instinct might be to binary search each row for the target. That works. With m rows and n columns, you run binary search m times, each costing O(log n). The total is O(m log n), which is decent but not optimal.

You can also binary search each column for O(n log m). Either way, you are not using the full power of the sorted structure. The matrix gives you information in two directions, and binary search on one dimension ignores the other.

The staircase approach

Here is the insight: stand at the top-right corner of the matrix. At position (0, n-1), you are looking at a value that is the largest in its row and the smallest in its column. This gives you a decision point.

• If the value equals the target, you are done.
• If the value is greater than the target, the target cannot be anywhere in this column (everything below is even larger). Eliminate the column by moving left.
• If the value is less than the target, the target cannot be anywhere in this row (everything to the left is even smaller). Eliminate the row by moving down.

Each comparison eliminates either an entire row or an entire column. Since there are m rows and n columns, you make at most m + n comparisons before you either find the target or run out of matrix. That is O(m + n) time.

The name "staircase search" comes from the path you trace through the matrix. Starting at the top-right and moving left or down, the path looks like a descending staircase.

The code

Here is the complete Python solution for LeetCode 240:

def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False

    row = 0
    col = len(matrix[0]) - 1

    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1

    return False

You start at row = 0, col = n - 1, the top-right corner. The while loop continues as long as both row and col are within bounds. At each step, you compare the current cell to the target and move accordingly. If you exit the loop, the target is not in the matrix.

That is the entire solution. No recursion, no extra data structures, no index math. Just two pointers walking through the matrix.

Visual walkthrough

Let us trace through the search for target = 5 in the matrix. We start at the top-right corner and follow the staircase path.

Five comparisons to find the target in a 25-element matrix. The path moved left three times (eliminating columns 4, 3, and 2) and down once (eliminating row 0) before landing on the target. At most, you would make 5 + 5 = 10 comparisons in this 5x5 matrix.

Complexity analysis

Time: O(m + n). Each step either increments row or decrements col. Since row can go from 0 to m - 1 and col can go from n - 1 to 0, the total number of steps is at most m + n. Each step does O(1) work.

Space: O(1). Two variables: row and col. No extra storage needed.

For a square matrix where m = n, the staircase approach is O(n) compared to O(n log n) for binary search per row. The improvement matters when the matrix is large.

The building blocks

This problem relies on two reusable ideas.

Corner-based elimination. When a matrix is sorted in two directions, the corners are your entry points. The top-right and bottom-left corners each give you a clear decision at every step: go one way to increase the value, go the other way to decrease it. This pattern shows up in any problem where you need to search a matrix with sorted rows and sorted columns.

Row/column elimination. Instead of narrowing down to a single cell through halving (like binary search), you eliminate an entire row or column at each step. This is powerful because a single comparison removes n or m candidates at once. The same reasoning applies in problems where you need to count elements in a sorted matrix or find the kth smallest element.

row = 0
col = len(matrix[0]) - 1

while row < len(matrix) and col >= 0:
    if matrix[row][col] > target:
        col -= 1
    elif matrix[row][col] < target:
        row += 1
    else:
        return True

Once you internalize the staircase pattern, you can apply it without rederiving the logic. The two-pointer walk from the corner is the core technique.

Edge cases to watch for

• Single element: matrix = [[5]], target = 5. You start at (0, 0), find the match immediately, and return True. Also test when the target does not match.
• Target not present: matrix = [[1,4,7],[2,5,8],[3,6,9]], target = 10. You walk down column 2, reach row 2, then walk left to column 0. All values are less than 10, and you exit the bounds. Return False.
• Target in the top-left corner: target = 1. You start at the top-right and walk left across the entire first row until you reach (0, 0). Found.
• Target in the bottom-right corner: target = 30. You start at the top-right and walk down the entire last column until you reach (4, 4). Found.
• Single row: matrix = [[1,3,5,7]]. The staircase search degenerates into a linear scan from right to left. Still correct, still O(n).
• Single column: matrix = [[1],[3],[5]]. The search walks down from (0, 0). Still correct, still O(m).
• Empty matrix: matrix = [] or matrix = [[]]. The guard clause at the top catches this and returns False.

From understanding to recall

You understand the staircase approach now: start at a corner, compare, move left or down. But in an interview, you need to remember which corner to start from and which direction to move for each comparison. Is it top-right or top-left? Do you go left when the value is bigger or smaller?

The mental model is simple. You want a starting position where one direction increases the value and the other direction decreases it. The top-right corner gives you that: left decreases (same row, smaller column), down increases (same column, larger row). If you start at the top-left, both right and down increase the value, and you have no way to make a useful decision.

Spaced repetition locks this in. Practice the solution today, again in two days, then in a week. After a few rounds, you will not need to rethink the corner choice or the movement directions. Your hands will write row = 0; col = len(matrix[0]) - 1 automatically.

Related posts

• Search a 2D Matrix: Binary Search on a Flattened Grid - The predecessor problem where the matrix can be treated as a single sorted array
• Binary Search: More Than Finding a Number - The full guide to binary search patterns, including search on the answer space
• Search in Rotated Sorted Array: Modified Binary Search - Another problem where structure guides the search direction