Search a 2D Matrix II Solution

Problem

You have a matrix where every row is sorted left to right and every column is sorted top to bottom, but the last element of a row is NOT necessarily smaller than the first element of the next row. Given a target value, return true if it exists anywhere in the 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

Input: matrix above, target = 5
Output: true
Explanation: 5 is found at row 1, column 1.

A counter-example: target = 20 returns false — 20 would fall between 19 and 21 in any column scan, but no cell holds exactly 20.

Intuition

The top-right corner is a pivot: it's the largest value in its row and the smallest in its column. If the target is smaller, the entire column can be ruled out (move left). If the target is larger, the entire row can be ruled out (move down). Each comparison eliminates a full row or column, so the search takes at most m + n steps — far better than checking every cell.

Approach 1 — Brute Force

Scan every cell in reading order and return true as soon as the target is found.

Iterate over each row.
Iterate over each element in the row.
Return true if the element equals the target.
Return false after all cells are checked.

1from typing import List
2
3class Solution:
4    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
5        for row in matrix:
6            for value in row:
7                if value == target:
8                    return True
9        return False

Time: O(m·n) — every cell is visited in the worst case. Space: O(1) — no extra storage.

Approach 2 — Staircase Search

Start at the top-right corner and use the sorted structure to eliminate a row or column at each step.

Position row = 0, col = numCols - 1 (top-right corner).
While row and col are in bounds, read current = matrix[row][col].
If current == target, return true.
If current > target, decrement col — the entire current column is ruled out.
If current < target, increment row — the entire current row is ruled out.
Return false if the pointer walks off the matrix.

1from typing import List
2
3class Solution:
4    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
5        num_rows, num_cols = len(matrix), len(matrix[0])
6        row, col = 0, num_cols - 1  # top-right corner is the pivot
7
8        while row < num_rows and col >= 0:
9            current = matrix[row][col]
10            if current == target:
11                return True
12            elif current > target:
13                col -= 1  # whole column is too large; eliminate it
14            else:
15                row += 1  # whole row is too small; eliminate it
16
17        return False

Time: O(m + n) — each step eliminates a row or a column, so at most m + n steps total. Space: O(1) — two pointers, no extra allocations.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(m·n)	O(1)	Acceptable when the matrix is tiny and code simplicity matters
Staircase Search	O(m + n)	O(1)	Always preferred; this is the intended solution

Common Mistakes

Applying the Search a 2D Matrix I trick here: The first matrix problem treats the grid as a single sorted array and runs binary search on a virtual index. This matrix breaks that property — the last element of row 0 can be larger than the first element of row 1 — so that approach gives wrong answers.
Starting from the top-left or bottom-right corner: From the top-left, both right and down increase the value, so you cannot eliminate a row or column with a single comparison. The pivot must be a corner where one direction increases and the other decreases — top-right or bottom-left.
Reversing the elimination direction: When current > target from the top-right, you eliminate the column by moving left (col--), not the row (row++). Swapping these causes the pointer to run off the matrix immediately or miss the target.
Wrong while-loop bounds: The loop condition must be col >= 0, not col < numCols. After starting at numCols - 1 and only decrementing, the valid range is [0, numCols-1]; the out-of-bounds exit is col < 0.
Returning false too early for the boundary case: If the target equals the minimum (top-left) or maximum (bottom-right) of the matrix, the staircase still finds it — but only if the loop runs until row < numRows && col >= 0, not until either bound is exceeded.

Search a 2D Matrix II — Solution