Matrix Search — Sorted Matrix

Before we start

By the end of this page you will be able to:

• See why starting from the top-right corner of a sorted matrix gives you two elimination choices at every step.
• Explain out loud why each comparison eliminates an entire row or column — not just a single cell.
• Recognise this staircase pattern whenever a problem gives you a 2D matrix sorted by both row and column.

Stop at every Pause & Think box — the insight here is a direct cousin of the opposite-end two pointers you already know.

Picture this first (no code yet)

That librarian's walk — start at the top-right corner, eliminate a column if too expensive, eliminate a row if too cheap — is the Sorted Matrix Search pattern.

The actual problem

You are given an m × n matrix where every row is sorted left-to-right and every column is sorted top-to-bottom. Given a target value, return true if it exists in the matrix, false otherwise.

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

target = 5  →  true
target = 20 →  false

First, the slow way (so you feel the pain)

Brute force: check every cell.

for row in matrix:
    for val in row:
        if val == target:
            return True
return False

O(m × n) — for a 1000×1000 matrix, that's a million checks.

Binary search on each row: since each row is sorted, binary-search it.

import bisect
for row in matrix:
    idx = bisect.bisect_left(row, target)
    if idx < len(row) and row[idx] == target:
        return True
return False

O(m log n) — better, but still visits every row. For a square n×n matrix: O(n log n).

The staircase search does it in O(m + n) — for a 1000×1000 matrix, that's 2000 checks instead of 1,000,000.

The turning point

The key question: which corner should you start from?

Top-left (1): If target > 1, should you go right or down? Both directions increase — you can't choose. Stuck.

Bottom-right (17): If target < 17, should you go left or up? Both directions decrease — again stuck.

Top-right (11): If target < 11, you know the entire right column from this cell downward is too large (they're all ≥ 11). Step left. If target > 11, you know the entire top row from this cell leftward is too small (they're all ≤ 11). Step down. One useful decision every time.

Bottom-left works the same way but mirrored.

Start from a corner that has one direction larger and one direction smaller — that's top-right or bottom-left.

The one idea to remember

Watch it happen, frame by frame

Matrix (same as above), target = 5. Starting position: row=0, col=3 (top-right, value=11).

(0,3)=11  >  5  →  too big,  step LEFT.   col=2
(0,2)= 7  >  5  →  too big,  step LEFT.   col=1
(0,1)= 4  <  5  →  too small, step DOWN.  row=1
(1,1)= 5  =  5  →  FOUND ✓

Now try target = 20 (not in the matrix):

(0,3)=11  < 20  →  too small, step DOWN.  row=1
(1,3)=12  < 20  →  too small, step DOWN.  row=2
(2,3)=16  < 20  →  too small, step DOWN.  row=3
(3,3)=17  < 20  →  too small, step DOWN.  row=4
row=4 ≥ m=4  →  out of bounds, STOP.  return False ✓

(0,3)=11  < 14  →  too small, step DOWN.  row=1
(1,3)=12  < 14  →  too small, step DOWN.  row=2
(2,3)=16  > 14  →  too big,  step LEFT.   col=2
(2,2)= 9  < 14  →  too small, step DOWN.  row=3
(3,2)=14  = 14  →  FOUND ✓

Now, the code — line by line

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

    row = 0                          # start at the top row
    col = len(matrix[0]) - 1         # start at the rightmost column (top-right corner)

    while row < len(matrix) and col >= 0:       # stay inside the matrix
        val = matrix[row][col]

        if val == target:
            return True              # found it
        elif val > target:
            col -= 1                 # too big — eliminate this column, step left
        else:
            row += 1                 # too small — eliminate this row, step down

    return False                     # pointer walked off the edge — not found

Mapping every line to the library story:

• row = 0, col = len(matrix[0]) - 1 — walk to the top-right shelf.
• while row < len(matrix) and col >= 0: — stay inside the library. Walk off the bottom (row ≥ m) or off the left (col < 0) and the book isn't here.
• val > target: col -= 1 — this shelf's price is too high. Every book below on this aisle is higher still — discard the entire rightmost remaining aisle.
• val < target: row += 1 — this book is too cheap. Every book to the left is cheaper still — discard the entire top remaining shelf.

Why does it never miss the target?

At every step we eliminate a row or column only after proving every remaining cell in it cannot be the target:

• We eliminate column col when matrix[row][col] > target. Since columns are sorted top-to-bottom, every cell below (row, col) in this column is ≥ matrix[row][col] > target. So none of them can be the target.
• We eliminate row row when matrix[row][col] < target. Since rows are sorted left-to-right, every cell to the left of (row, col) in this row is ≤ matrix[row][col] < target. So none of them can be the target.

Every elimination is guaranteed junk. The target, if it exists, is always still inside the remaining sub-matrix.

Time: O(m + n) — row can increase at most m times; col can decrease at most n times. Total steps ≤ m + n.

Space: O(1) — just two integer pointers.

When should I reach for this? (the trigger list)

Reach for the top-right (or bottom-left) staircase search when:

• The matrix is sorted both row-wise and column-wise.
• You're asked to find, count, or decide existence of a value in such a matrix.
• Brute force is O(m × n) and the interviewer asks for better.
• The problem resembles "Search a 2D Matrix" or "Count elements less than X in a sorted matrix."

A tell-tale sign: the matrix guarantees that every row is sorted AND every column is sorted. That combination is the gift that allows the staircase.

The same trick in three disguises

Disguise 1 — Count elements ≤ target in each row

For each row, binary-search for the insertion point of target. Since rows are sorted, bisect_right(row, target) gives the count in O(log n) per row. But using the staircase idea you can also count globally in O(m + n):

def countLessEqual(matrix, target):
    # Start at bottom-left: largest in row, smallest in column
    row, col = len(matrix) - 1, 0
    count = 0
    while row >= 0 and col < len(matrix[0]):
        if matrix[row][col] <= target:
            count += row + 1    # all cells above (row,col) in this column qualify
            col += 1
        else:
            row -= 1
    return count

Notice: we start from bottom-left here (smallest in row, largest in column) — the mirrored variant.

Disguise 2 — Kth Smallest in a Sorted Matrix (LC #378)

Binary search on value range, use staircase to count elements ≤ mid in O(m + n) per binary-search step.

def kthSmallest(matrix, k):
    n = len(matrix)
    lo, hi = matrix[0][0], matrix[-1][-1]

    def count_le(mid):
        row, col = 0, n - 1
        cnt = 0
        while row < n and col >= 0:
            if matrix[row][col] <= mid:
                cnt += col + 1   # all elements in this row up to col qualify
                row += 1
            else:
                col -= 1
        return cnt

    while lo < hi:
        mid = (lo + hi) // 2
        if count_le(mid) < k:
            lo = mid + 1
        else:
            hi = mid
    return lo

Traps that catch beginners

Say it like a pro (interview one-liner)

"Since both rows and columns are sorted, I'll use the staircase search — start at the top-right corner where I have one direction that gets larger and one that gets smaller. If the value is too big I step left, eliminating this column; if too small I step down, eliminating this row. Each step eliminates a full row or column, giving O(m + n) time and O(1) space."

row, col = 0, n-1
while row < m and col >= 0:
    if val == target: found
    elif val > target: col -= 1
    else: row += 1

Check yourself

Practice problems

When you can write the staircase loop from memory and explain why you start at top-right and not top-left, you've learned this pattern.

Next up: In-Place Array Manipulation — where the array itself becomes your notebook, using negation to mark visited cells without extra memory.