Searching in 2D - Learning Module

Loading content...

0/276

Staircase Search Algorithm

The Elegant O(m + n) Solution

In a row-and-column-sorted matrix, brute-force search requires O(m × n) comparisons—examining every element until we find the target or exhaust the matrix. But the sorted structure contains far more information than we're using. Surely, we can do better.

The staircase search algorithm (also called the corner search or saddleback search) achieves O(m + n) time complexity—a dramatic improvement. For a 1000×1000 matrix, this means at most 2000 comparisons instead of 1,000,000.

The algorithm's beauty lies in its simplicity: start at a corner, make exactly one comparison, and eliminate either an entire row or an entire column. Repeat until you find the target or exhaust the search space. This page will develop this algorithm from first principles, prove its correctness, and explore its implementation details.

What You Will Master

By the end of this page, you will understand why the top-right and bottom-left corners are special positions, implement the staircase search algorithm from scratch, prove its correctness using loop invariants, and analyze why it achieves O(m + n) time complexity.

The Key Insight — Strategic Corners

In a row-and-column-sorted matrix, not all positions are created equal. Let's analyze what information each position provides:

The Four Corners:

Consider a matrix where rows increase left-to-right and columns increase top-to-bottom:

    Col 0  Col 1  Col 2  Col 3
    ↓      ↓      ↓      ↓
   [1      4      7      11]  ← Row 0
   [2      5      8      12]  ← Row 1
   [3      6      9      16]  ← Row 2
   [10     13     14     17]  ← Row 3

Let's examine each corner:

Corner Position Analysis
Corner	Value	Row Extreme	Column Extreme	Search Value?
Top-Left (0,0)	1	Row minimum	Column minimum	❌ No decision possible
Top-Right (0,3)	11	Row maximum	Column minimum	✓ Can eliminate row OR column
Bottom-Left (3,0)	10	Row minimum	Column maximum	✓ Can eliminate row OR column
Bottom-Right (3,3)	17	Row maximum	Column maximum	❌ No decision possible

Why Top-Left and Bottom-Right Don't Work:

Top-Left (global minimum): If target > M[0][0], we can only conclude the target might be anywhere else—we can't eliminate any row or column. If target < M[0][0], the target doesn't exist.
Bottom-Right (global maximum): If target < M[m-1][n-1], we can only conclude target might be anywhere else. If target > M[m-1][n-1], it doesn't exist.

Why Top-Right and Bottom-Left ARE Special:

Top-Right M[0][n-1]: This position is simultaneously:
- The maximum of row 0 (all elements to its left are smaller)
- The minimum of column n-1 (all elements below are larger)
This dual role enables binary decisions:
- If target < M[0][n-1]: Target can't be in column n-1 → eliminate column, move left
- If target > M[0][n-1]: Target can't be in row 0 → eliminate row, move down
- If target == M[0][n-1]: Found!
Bottom-Left M[m-1][0]: The symmetric case:
- Maximum of column 0, minimum of row m-1
- Enables similar binary decisions with left/up movements

The Saddlepoint Analogy

In mathematics, a saddlepoint is a position that's simultaneously a minimum in one direction and a maximum in another—like the center of a horse saddle. The top-right and bottom-left corners of a row-and-column sorted matrix are saddlepoints: maximum in one dimension, minimum in the other. This property is exactly what enables efficient search.

The Algorithm — Step by Step

Let's develop the staircase search algorithm starting from the top-right corner. The bottom-left variant follows the same logic with mirrored directions.

Algorithm: Staircase Search (Top-Right Start)

Input: Row-and-column-sorted matrix M[m][n], target value T
Output: (row, col) if T found, (-1, -1) otherwise

1. Start at position (row, col) = (0, n-1)  // Top-right corner
2. While row < m AND col >= 0:
   a. Let current = M[row][col]
   b. If current == T:
      Return (row, col)  // Found!
   c. Else if current > T:
      col = col - 1      // Move left (eliminate column)
   d. Else: // current < T
      row = row + 1      // Move down (eliminate row)
3. Return (-1, -1)  // Not found

The algorithm traces a staircase path from the top-right toward the bottom-left, never backtracking, until it finds the target or exits the matrix bounds.

staircase_search.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
def staircase_search(matrix, target):
    """
    Search for target in a row-and-column-sorted matrix.
    
    Starts at top-right corner and moves:
    - LEFT if current value > target (eliminate current column)
    - DOWN if current value < target (eliminate current row)
    
    Time Complexity: O(m + n)
    Space Complexity: O(1)
    
    Args:
        matrix: 2D list where rows and columns are sorted in ascending order
        target: Value to search for
        
    Returns:
        (row, col) tuple if found, (-1, -1) if not found
    """
    if not matrix or not matrix[0]:
        return (-1, -1)
    
    m, n = len(matrix), len(matrix[0])
    
    # Start at top-right corner
    row, col = 0, n - 1
    
    while row < m and col >= 0:
        current = matrix[row][col]
        
        if current == target:
            return (row, col)  # Found!
        elif current > target:
            # Target can't be in this column (all below are even larger)
            col -= 1  # Move left
        else:  # current < target
            # Target can't be in this row (all to the left are even smaller)
            row += 1  # Move down
    
    return (-1, -1)  # Target not in matrix
 
 
# Test with example matrix
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]
]
 
# Test cases
print(staircase_search(matrix, 9))    # (2, 2) - found
print(staircase_search(matrix, 5))    # (1, 1) - found
print(staircase_search(matrix, 20))   # (-1, -1) - not found
print(staircase_search(matrix, 1))    # (0, 0) - found (corner case)
print(staircase_search(matrix, 30))   # (4, 4) - found (corner case)

The Path Forms a Staircase

The algorithm's name comes from the shape of the path traced: starting top-right and moving only left or down creates a staircase pattern descending toward the bottom-left. Each step either goes left (horizontal tread) or down (vertical riser), never diagonally or backwards.

Visual Walkthrough

Let's trace through the algorithm searching for target = 14 in our example matrix:

Matrix:                    Search for: 14
   [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]

Step-by-Step Trace:

Staircase Search Trace for target = 14
Step	Position	Value	Comparison	Action	Eliminated
1	(0, 4)	15	15 > 14	Move left	Column 4
2	(0, 3)	11	11 < 14	Move down	Row 0
3	(1, 3)	12	12 < 14	Move down	Row 1
4	(2, 3)	16	16 > 14	Move left	Column 3
5	(2, 2)	9	9 < 14	Move down	Row 2
6	(3, 2)	14	14 == 14	FOUND!	—

staircase_trace.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def staircase_search_with_trace(matrix, target):
    """
    Staircase search with detailed trace output.
    """
    if not matrix or not matrix[0]:
        return (-1, -1)
    
    m, n = len(matrix), len(matrix[0])
    row, col = 0, n - 1
    step = 0
    
    print(f"Searching for {target} in {m}x{n} matrix")
    print(f"Starting at top-right corner: ({row}, {col})")
    print("-" * 60)
    
    while row < m and col >= 0:
        step += 1
        current = matrix[row][col]
        
        print(f"Step {step}: Position ({row}, {col}) = {current}", end="")
        
        if current == target:
            print(f" → FOUND!")
            return (row, col)
        elif current > target:
            print(f" > {target} → Move LEFT (eliminate column {col})")
            col -= 1
        else:
            print(f" < {target} → Move DOWN (eliminate row {row})")
            row += 1
    
    print(f"Exited bounds at ({row}, {col}) → NOT FOUND")
    return (-1, -1)
 
 
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]
]
 
# Trace the search
result = staircase_search_with_trace(matrix, 14)
print(f"\nResult: {result}")

Visual Path (X marks the path, T marks the target):

   [.   .   .   .   ①]     ① Start: 15 > 14, go left
   [.   .   .   ②  ←]     ② 11 < 14, go down  
   [.   .   .   ③  .]     ③ 12 < 14, go down
   [.   .   T   ④  .]     ④ 16 > 14, go left
   [.   .   ↑   ↓  .]     ⑤ 9 < 14, go down
                          ⑥ 14 = 14, FOUND!

Actual path: (0,4) → (0,3) → (1,3) → (2,3) → (2,2) → (3,2) ✓

Notice how the path never backtracks—it only moves left or down, creating the characteristic staircase shape.

Correctness Proof

To prove the algorithm is correct, we need to establish:

If the target exists in the matrix, the algorithm will find it.
If the algorithm reports 'not found,' the target truly doesn't exist.

We'll use a loop invariant to prove both properties.

Loop Invariant:

At the start of each iteration, if the target exists in the matrix, it exists in the submatrix M[row...m-1][0...col] (the region from current position to bottom-left corner).

Initialization (base case):

Before the first iteration: row = 0, col = n - 1. The submatrix M[0...m-1][0...n-1] is the entire matrix. If target exists, it's in this region. ✓

Maintenance (inductive step):

Assume the invariant holds at the start of an iteration. We have three cases:

Case 1: M[row][col] == target

We return the position. Correct!

Case 2: M[row][col] > target

We move left: col = col - 1
Why is this safe? All elements in column col below position (row, col) are even larger than M[row][col] (column-sorted property). Since M[row][col] > target, the entire column can be eliminated.
The target (if it exists) must be in M[row...m-1][0...col-1]. ✓

Case 3: M[row][col] < target

We move down: row = row + 1
Why is this safe? All elements in row row to the left of position (row, col) are even smaller than M[row][col] (row-sorted property). Since M[row][col] < target, the entire row can be eliminated.
The target (if it exists) must be in M[row+1...m-1][0...col]. ✓

Termination:

The loop terminates when row ≥ m OR col < 0, meaning the search space is empty. If we haven't found the target, it doesn't exist.

invariant_verification.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
def staircase_search_with_invariant_check(matrix, target):
    """
    Staircase search with loop invariant assertions.
    
    Invariant: If target exists, it's in M[row:m][0:col+1]
    """
    if not matrix or not matrix[0]:
        return (-1, -1)
    
    m, n = len(matrix), len(matrix[0])
    row, col = 0, n - 1
    
    def target_could_exist_in_region(r_start, r_end, c_start, c_end):
        """Check if target could exist in the specified submatrix."""
        for i in range(r_start, r_end):
            for j in range(c_start, c_end):
                if matrix[i][j] == target:
                    return True
        return False
    
    # Ground truth: does target actually exist?
    target_exists = target_could_exist_in_region(0, m, 0, n)
    
    iteration = 0
    while row < m and col >= 0:
        iteration += 1
        
        # Check loop invariant
        region_contains_target = target_could_exist_in_region(row, m, 0, col + 1)
        
        if target_exists:
            assert region_contains_target, \
                f"Invariant violated at iteration {iteration}!"
        
        current = matrix[row][col]
        
        if current == target:
            print(f"Found at ({row}, {col}) after {iteration} iterations")
            return (row, col)
        elif current > target:
            col -= 1
        else:
            row += 1
    
    print(f"Not found after {iteration} iterations")
    
    # If we exit without finding, target shouldn't exist
    if target_exists:
        raise AssertionError("Algorithm failed to find existing target!")
    
    return (-1, -1)
 
 
# Test the invariant
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]
]
 
staircase_search_with_invariant_check(matrix, 14)  # Should find
staircase_search_with_invariant_check(matrix, 20)  # Should not find

Invariants as Thinking Tools

Loop invariants aren't just for formal proofs—they're powerful debugging tools. If your search algorithm gives wrong results, check whether the invariant holds after each step. A violated invariant immediately pinpoints where the logic is flawed.

The Bottom-Left Variant

The algorithm works equally well starting from the bottom-left corner, with mirrored movement directions:

Bottom-Left Algorithm:

1. Start at (row, col) = (m-1, 0)  // Bottom-left corner
2. While row >= 0 AND col < n:
   a. If M[row][col] == target: Return (row, col)
   b. If M[row][col] > target: row--  // Move up
   c. If M[row][col] < target: col++  // Move right
3. Return (-1, -1)

The bottom-left position M[m-1][0] is:

The minimum of row m-1 (all right elements are larger)
The maximum of column 0 (all elements above are smaller)

This dual role enables the same binary elimination logic.

bottom_left_variant.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
def staircase_search_bottom_left(matrix, target):
    """
    Staircase search starting from bottom-left corner.
    
    Moves:
    - RIGHT if current value < target (eliminate current row's left portion)
    - UP if current value > target (eliminate current column's bottom portion)
    
    Time Complexity: O(m + n)
    Space Complexity: O(1)
    """
    if not matrix or not matrix[0]:
        return (-1, -1)
    
    m, n = len(matrix), len(matrix[0])
    
    # Start at bottom-left corner
    row, col = m - 1, 0
    
    while row >= 0 and col < n:
        current = matrix[row][col]
        
        if current == target:
            return (row, col)
        elif current > target:
            # Target can't be in this row's remaining portion or below
            row -= 1  # Move up
        else:  # current < target
            # Target can't be in this column's remaining portion or above
            col += 1  # Move right
    
    return (-1, -1)
 
 
# Both variants produce the same result
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]
]
 
# Compare top-right vs bottom-left
def staircase_top_right(matrix, target):
    if not matrix or not matrix[0]:
        return (-1, -1)
    m, n = len(matrix), len(matrix[0])
    row, col = 0, n - 1
    while row < m and col >= 0:
        if matrix[row][col] == target:
            return (row, col)
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1
    return (-1, -1)
 
for target in [5, 9, 14, 20, 30]:
    tr = staircase_top_right(matrix, target)
    bl = staircase_search_bottom_left(matrix, target)
    print(f"Target {target}: top-right → {tr}, bottom-left → {bl}")
    assert tr == bl, "Results should match!"

Top-Right Approach

•Start: (0, n-1)
•Value > target: move LEFT
•Value < target: move DOWN
•Path: descends toward bottom-left
•Eliminates columns going left
•Eliminates rows going down

Bottom-Left Approach

•Start: (m-1, 0)
•Value > target: move UP
•Value < target: move RIGHT
•Path: ascends toward top-right
•Eliminates rows going up
•Eliminates columns going right

Which Variant to Choose?

Both variants have identical time complexity. Choose based on convention or problem constraints. The top-right variant is often preferred in interviews because it starts with row=0, which some find more intuitive. Some problems (like counting elements) may benefit from one direction over the other.

Time and Space Complexity Analysis

Let's rigorously analyze the algorithm's efficiency.

Time Complexity: O(m + n)

Proof: At each iteration, the algorithm either:

Decrements col by 1 (moves left), OR
Increments row by 1 (moves down)

The algorithm terminates when row ≥ m OR col < 0.

col can decrease at most n times (from n-1 to -1)
row can increase at most m times (from 0 to m)

Therefore, the total number of iterations is at most m + n.

Each iteration performs O(1) work:

One comparison
One index update

Total: O(m + n) time.

Space Complexity: O(1)

The algorithm uses only a constant number of variables:

row and col for position tracking
current for the current element value
m and n for dimensions

No additional data structures are created. The algorithm operates directly on the input matrix without modification.

Total: O(1) auxiliary space.

Complexity Comparison with Alternatives
Algorithm	Time Complexity	Space Complexity	Best For
Brute Force	O(m × n)	O(1)	Unsorted matrices
Binary Search per Row	O(m × log n)	O(1)	Row-sorted only
Binary Search per Column	O(n × log m)	O(1)	Column-sorted only
Staircase Search	O(m + n)	O(1)	Row-and-column sorted
Binary Search (1D)	O(log(m×n))	O(1)	Fully sorted matrix

complexity_comparison.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import time
import random
 
def brute_force_search(matrix, target):
    """O(m × n) brute force search."""
    for i, row in enumerate(matrix):
        for j, val in enumerate(row):
            if val == target:
                return (i, j)
    return (-1, -1)
 
def binary_search_per_row(matrix, target):
    """O(m × log n) binary search each row."""
    for i, row in enumerate(matrix):
        left, right = 0, len(row) - 1
        while left <= right:
            mid = (left + right) // 2
            if row[mid] == target:
                return (i, mid)
            elif row[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
    return (-1, -1)
 
def staircase_search(matrix, target):
    """O(m + n) staircase search."""
    if not matrix or not matrix[0]:
        return (-1, -1)
    m, n = len(matrix), len(matrix[0])
    row, col = 0, n - 1
    while row < m and col >= 0:
        if matrix[row][col] == target:
            return (row, col)
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1
    return (-1, -1)
 
def create_sorted_matrix(m, n):
    """Create a row-and-column sorted m×n matrix."""
    # Simple approach: use coordinates as values
    return [[i * n + j for j in range(n)] for i in range(m)]
 
def benchmark(m, n, trials=100):
    """Compare algorithm performance."""
    matrix = create_sorted_matrix(m, n)
    max_val = m * n - 1
    
    # Random targets (mix of existing and non-existing)
    targets = [random.randint(0, max_val + 10) for _ in range(trials)]
    
    results = {}
    
    for name, func in [
        ("Brute Force", brute_force_search),
        ("Binary/Row", binary_search_per_row),
        ("Staircase", staircase_search)
    ]:
        start = time.perf_counter()
        for t in targets:
            func(matrix, t)
        elapsed = time.perf_counter() - start
        results[name] = elapsed * 1000  # Convert to ms
    
    print(f"Matrix: {m}×{n} = {m*n:,} elements, {trials} searches")
    for name, ms in results.items():
        print(f"  {name:12}: {ms:.3f} ms")
    print()
 
# Run benchmarks
for size in [100, 500, 1000]:
    benchmark(size, size)

Practical Performance

For a 1000×1000 matrix, staircase search makes at most 2000 comparisons. Brute force makes up to 1,000,000. Even with constant factor overheads, staircase search is orders of magnitude faster for large matrices. The difference becomes even more dramatic as matrix dimensions grow.

Common Variations and Extensions

The staircase search pattern can be adapted for several related problems:

1. Count Occurrences: If the matrix can contain duplicates and we need to count how many times the target appears, we can't stop at the first match. However, finding all occurrences requires more careful handling.

2. Count Elements Less Than / Greater Than: A powerful variation counts elements satisfying a comparison condition.

3. Find Kth Smallest Element: Used as a subroutine in algorithms that binary search on value.

4. Range Queries: Find all elements in a given value range.

staircase_variations.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
def count_less_than_or_equal(matrix, target):
    """
    Count elements ≤ target in a row-and-column sorted matrix.
    Uses staircase search from bottom-left.
    
    Time: O(m + n)
    """
    if not matrix or not matrix[0]:
        return 0
    
    m, n = len(matrix), len(matrix[0])
    count = 0
    
    # Start from bottom-left
    row, col = m - 1, 0
    
    while row >= 0 and col < n:
        if matrix[row][col] <= target:
            # All elements in this column from row 0 to current row are ≤ target
            count += row + 1
            col += 1  # Move to next column
        else:
            # Current element is too large, move up
            row -= 1
    
    return count
 
 
def count_negatives(matrix):
    """
    Count negative numbers in a sorted matrix.
    LeetCode 1351: https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/
    
    Note: This problem has rows sorted in DECREASING order.
    Adaptation: start from top-left instead.
    """
    if not matrix or not matrix[0]:
        return 0
    
    m, n = len(matrix), len(matrix[0])
    count = 0
    
    # For decreasing order, start from bottom-left
    # and look for the transition point
    row, col = m - 1, 0
    
    while row >= 0 and col < n:
        if matrix[row][col] < 0:
            # All elements to the right in this row are also negative
            count += n - col
            row -= 1  # Move up to next row
        else:
            col += 1  # Move right to find negatives
    
    return count
 
 
def find_kth_smallest_count_based(matrix, k):
    """
    Find the kth smallest element using binary search on value
    with staircase counting as subroutine.
    
    Time: O((m + n) × log(max - min))
    """
    if not matrix or not matrix[0]:
        return None
    
    m, n = len(matrix), len(matrix[0])
    lo, hi = matrix[0][0], matrix[m-1][n-1]
    
    while lo < hi:
        mid = (lo + hi) // 2
        count = count_less_than_or_equal(matrix, mid)
        
        if count < k:
            lo = mid + 1
        else:
            hi = mid
    
    return lo
 
 
# Test
matrix = [
    [1,   5,   9],
    [10,  11,  13],
    [12,  13,  15]
]
 
print(f"Elements ≤ 10: {count_less_than_or_equal(matrix, 10)}")  # 4
print(f"4th smallest: {find_kth_smallest_count_based(matrix, 4)}")  # 10

The Counting Insight

When counting elements ≤ target using bottom-left staircase, each rightward step adds (row + 1) elements to the count because the entire column above (including current row) is ≤ target. This gives O(m + n) counting—essential for problems like 'Kth Smallest Element in a Sorted Matrix.'

Common Pitfalls and Edge Cases

Despite its simplicity, staircase search has several common pitfalls:

1. Wrong Starting Corner: Starting from top-left or bottom-right doesn't work—you can't make a binary decision from these positions.

2. Boundary Conditions: Ensure loop conditions handle matrix edges correctly.

3. Empty Matrix Handling: Always check for null/empty matrix before accessing elements.

4. Single Row/Column Matrices: The algorithm degenerates gracefully to O(m) or O(n) linear search.

5. Duplicate Elements: The algorithm finds one occurrence, not all. The position found depends on the search path.

edge_cases.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
def robust_staircase_search(matrix, target):
    """
    Production-ready staircase search with comprehensive edge case handling.
    """
    # Edge case 1: Null or empty matrix
    if not matrix:
        return (-1, -1)
    if not matrix[0]:
        return (-1, -1)
    
    m, n = len(matrix), len(matrix[0])
    
    # Edge case 2: Target outside possible range
    if target < matrix[0][0] or target > matrix[m-1][n-1]:
        return (-1, -1)  # Quick rejection
    
    row, col = 0, n - 1
    
    while row < m and col >= 0:
        current = matrix[row][col]
        
        if current == target:
            return (row, col)
        elif current > target:
            col -= 1
        else:
            row += 1
    
    return (-1, -1)
 
 
# Test edge cases
def test_edge_cases():
    # Empty matrix
    assert robust_staircase_search([], 5) == (-1, -1)
    assert robust_staircase_search([[]], 5) == (-1, -1)
    
    # Single element
    assert robust_staircase_search([[5]], 5) == (0, 0)
    assert robust_staircase_search([[5]], 3) == (-1, -1)
    
    # Single row
    assert robust_staircase_search([[1, 2, 3, 4, 5]], 3) == (0, 2)
    assert robust_staircase_search([[1, 2, 3, 4, 5]], 6) == (-1, -1)
    
    # Single column
    assert robust_staircase_search([[1], [2], [3]], 2) == (1, 0)
    assert robust_staircase_search([[1], [2], [3]], 0) == (-1, -1)
    
    # Target at corners
    matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    assert robust_staircase_search(matrix, 1) == (0, 0)  # Top-left
    assert robust_staircase_search(matrix, 3) == (0, 2)  # Top-right
    assert robust_staircase_search(matrix, 7) == (2, 0)  # Bottom-left
    assert robust_staircase_search(matrix, 9) == (2, 2)  # Bottom-right
    
    # Target outside range (quick rejection)
    assert robust_staircase_search(matrix, 0) == (-1, -1)
    assert robust_staircase_search(matrix, 10) == (-1, -1)
    
    # Duplicates: finds one occurrence
    dup_matrix = [[1, 2, 2], [2, 2, 3], [2, 3, 4]]
    result = robust_staircase_search(dup_matrix, 2)
    assert dup_matrix[result[0]][result[1]] == 2  # Valid position found
    
    print("All edge cases passed!")
 
test_edge_cases()

Off-by-One Prevention

The most common bug is incorrect loop termination. Remember: 'row < m' (not ≤) and 'col >= 0' (not > 0). After the last valid column (col = 0), decrementing gives col = -1, which should exit the loop. Similarly for rows.

Summary: The Staircase Search Algorithm

The staircase search algorithm is a beautiful example of exploiting problem structure to achieve dramatic efficiency gains.

Key Takeaways

•Strategic corners matter: Top-right and bottom-left positions are saddlepoints—maximum in one dimension, minimum in another—enabling binary elimination decisions.
•Each comparison eliminates a row OR column: This guaranteed progress ensures O(m + n) worst-case performance.
•The algorithm never backtracks: Movement is monotonic (only left+down from top-right, or right+up from bottom-left), tracing a staircase path.
•Loop invariants prove correctness: The shrinking search region maintains the property that if the target exists, it's still reachable.
•Constant space required: Only a few index variables are needed—no auxiliary data structures.
•Variations enable counting and ranking: The staircase pattern extends to counting elements, finding kth smallest, and range queries.

What's Next:

Not all sorted matrices have the row-and-column-sorted property. The next page explores fully sorted matrices—where the entire matrix, read row by row, forms a sorted sequence. This stronger property enables converting the 2D search into a 1D binary search with O(log(m × n)) complexity.

Page Complete

You've mastered the staircase search algorithm—an elegant O(m + n) solution for row-and-column-sorted matrices. You understand why certain corners enable binary elimination, how to implement both top-right and bottom-left variants, and how to prove correctness using loop invariants. This algorithm is a staple of coding interviews and practical applications alike.