Search a 2D Matrix II (LeetCode 240)
Top-Right Pivot Elimination in Row/Column Sorted Grids
Given an matrix where every row is sorted left-to-right and every column is sorted top-to-bottom, search for a target value in optimal time and space.
The Technique Invariant: Instead of searching each row independently using binary search (), exploit the orthogonal gradients by starting at a Saddleback Corner—specifically top-right or bottom-left :
- At , moving left strictly decreases values, while moving down strictly increases values.
- If , eliminate the entire column by decrementing (all elements below are even larger).
- If , eliminate the entire row by incrementing (all elements to the left are even smaller). Each comparison permanently discards an entire row or column, guaranteeing convergence in at most steps.
Worked Examples
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 = 5truematrix = [[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 = 20false⚖️Formal Constraints & Bounds
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-109 <= matrix[i][j] <= 109All the integers in each row are sorted in ascending order
All the integers in each column are sorted in ascending order
-109 <= target <= 109
Why It Works & Core Invariant
If target < matrix[r][c] \implies \text{prune column } c; \text{ if } target > matrix[r][c] ⟹ prune row r.
Real-World Scenario & Production Applications
Geographic Information Systems (GIS) and 2D spatial indexing engines use saddleback contours to clip bounding boxes and polygon horizons in linear boundary scans.
| 1 | Initialize pivot at top-right corner: row = 0, col = n - 1 |
| 2 | While row < m and col >= 0, inspect matrix[row][col] |
| 3 | If current == target, return true |
| 4 | If current > target, prune current column (col--) |
| 5 | If current < target, prune current row (row++) |
Target: Search a 2D Matrix II (LeetCode 240). Saddle point selection: starting at the top-right corner allows moving left to decrease values and moving down to increase values.
Start at (0, N-1). If val > target, column c cannot contain target; decrement c. If val < target, row r cannot contain target; increment r.
r = 0, c = n - 1; while r < m and c >= 0: compare and step
Conceptual Narrative
The Flash of Genius: Standing at the top-right corner of a row-and-column sorted matrix turns search into an elimination walk that drops a whole row or column per comparison. If the current value exceeds the target, eliminate the entire column (col--); if smaller, eliminate the entire row (row++). Discards M + N cells in O(M + N) with zero memory.
The Mental Model Analogy: The Mountain Pass Saddle Ridge
Imagine standing at the exact saddle point of a mountain ridge—a topographic vantage point where walking North takes you uphill, walking South takes you downhill, walking East takes you uphill, and walking West takes you downhill. In a row-and-column sorted matrix, standing at the top-right corner is this exact saddle point! Looking left, values decrease monotonically; looking down, values increase monotonically. If you are hunting for a target value and you look at your current vantage point: if your current point is too large, the entire column below you is guaranteed to be even larger—you can blast away that whole column forever by stepping left! If your current point is too small, the entire row to your left is guaranteed to be even smaller—you can blast away that entire row forever by stepping down! With every single footstep, an entire mountain ridge evaporates from the map.
Pitfall: The top-right corner is a saddle point: all elements to its left are smaller; all elements below it are greater.
Pitfall: Each comparison unconditionally eliminates either 1 entire column or 1 entire row.
Pitfall: Total steps cannot exceed M + N.
4-Phase Thought Process Model
Senior SWE thought process architecture for Saddleback 2D Matrix Elimination.
Pattern Recognition Signals
The 10-second spot
The matrix has sorted rows and sorted columns. Starting at gives no decision boundary because both axes increase. Identify as the saddle point.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Maintain the invariant that the candidate target must lie in matrix[r..M-1][0..c]. Any cell outside this bounding box is mathematically proven not to contain target.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Loop guard:
while r < m and c >= 0:Return immediately upon match:
return TrueExhaustion return:
return False
The 60-Second Interview Pitch
Say this out loud before you type a single line
In each iteration, either increments or decrements. can increment at most times, and can decrement at most times. The total iterations are strictly bounded by .
Standing at the top-right corner of a row-and-column sorted matrix turns search into an elimination walk that drops a whole row or column per comparison. If the current value exceeds the target, eliminate the entire column (col--); if smaller, eliminate the entire row (row++). Discards M + N cells in O(M + N) with zero memory.
Complexity & Mathematical Proof
O(M + N)
The pointer r starts at 0 and can increment at most M times before violating r < M. The pointer c starts at N - 1 and can decrement at most N times before violating c >= 0. In each step of the while loop, exactly one pointer moves. The total number of loop iterations is at most M + N. Each iteration performs one array lookup and two integer comparisons (O(1)). Therefore, the total time complexity is strictly O(M + N).
O(1)
The algorithm uses exactly two integer variables (r and c) to store the current matrix coordinates. No auxiliary arrays, sets, or recursive call stack frames are allocated. Auxiliary space complexity is strictly O(1).
The pointer r starts at 0 and can increment at most M times before violating r < M. The pointer c starts at N - 1 and can decrement at most N times before violating c >= 0. In each step of the while loop, exactly one pointer moves. The total number of loop iterations is at most M + N. Each iteration performs one array lookup and two integer comparisons (O(1)). Therefore, the total time complexity is strictly O(M + N).
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Identifies why (0, 0) and (M-1, N-1) fail to provide a greedy decision rule. • Chooses either (0, N-1) or (M-1, 0) without hesitation and clearly states the elimination invariant. • Proves the maximum step count is M + N without hand-waving. • Analyzes memory cache locality: notes that column decrements (c -= 1) remain within the same row cache line, whereas row increments (r += 1) jump by stride N.
m == matrix.length. n == matrix[i].length. 1 <= n, m <= 300. -109 <= matrix[i][j] <= 109. All the integers in each row are sorted in ascending order. All the integers in each column are sorted in ascending order. -109 <= target <= 109
In spatial GIS indexing (e.g. Google Maps raster elevation grids, geohash bounding boxes), saddleback elimination quickly finds bounding contours across pre-sorted tile pyramids.
Core Algorithmic State Invariants
The search interval represents the candidate domain. Mid-point calculation and range shifts must shrink this space strictly monotonically without skipping candidate solutions.
The predicate function checks monotonic truth. If true, the candidate is a viable bound, allowing pruning of the discarded partition.
Convergence is guaranteed when the candidate interval reduces to size 1, returning the recorded boundary index without off-by-one errors.
Search a 2D Matrix II (LeetCode 240)
Top-Right Pivot Elimination in Row/Column Sorted Grids
Given an matrix where every row is sorted left-to-right and every column is sorted top-to-bottom, search for a target value in optimal time and space.
The Technique Invariant: Instead of searching each row independently using binary search (), exploit the orthogonal gradients by starting at a Saddleback Corner—specifically top-right or bottom-left :
- At , moving left strictly decreases values, while moving down strictly increases values.
- If , eliminate the entire column by decrementing (all elements below are even larger).
- If , eliminate the entire row by incrementing (all elements to the left are even smaller). Each comparison permanently discards an entire row or column, guaranteeing convergence in at most steps.
Worked Examples
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 = 5truematrix = [[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 = 20false⚖️Formal Constraints & Bounds
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-109 <= matrix[i][j] <= 109All the integers in each row are sorted in ascending order
All the integers in each column are sorted in ascending order
-109 <= target <= 109
Why It Works & Core Invariant
If target < matrix[r][c] \implies \text{prune column } c; \text{ if } target > matrix[r][c] ⟹ prune row r.
Real-World Scenario & Production Applications
Geographic Information Systems (GIS) and 2D spatial indexing engines use saddleback contours to clip bounding boxes and polygon horizons in linear boundary scans.
| 1 | Initialize pivot at top-right corner: row = 0, col = n - 1 |
| 2 | While row < m and col >= 0, inspect matrix[row][col] |
| 3 | If current == target, return true |
| 4 | If current > target, prune current column (col--) |
| 5 | If current < target, prune current row (row++) |
Target: Search a 2D Matrix II (LeetCode 240). Saddle point selection: starting at the top-right corner allows moving left to decrease values and moving down to increase values.
Start at (0, N-1). If val > target, column c cannot contain target; decrement c. If val < target, row r cannot contain target; increment r.
r = 0, c = n - 1; while r < m and c >= 0: compare and step
Conceptual Narrative
The Flash of Genius: Standing at the top-right corner of a row-and-column sorted matrix turns search into an elimination walk that drops a whole row or column per comparison. If the current value exceeds the target, eliminate the entire column (col--); if smaller, eliminate the entire row (row++). Discards M + N cells in O(M + N) with zero memory.
The Mental Model Analogy: The Mountain Pass Saddle Ridge
Imagine standing at the exact saddle point of a mountain ridge—a topographic vantage point where walking North takes you uphill, walking South takes you downhill, walking East takes you uphill, and walking West takes you downhill. In a row-and-column sorted matrix, standing at the top-right corner is this exact saddle point! Looking left, values decrease monotonically; looking down, values increase monotonically. If you are hunting for a target value and you look at your current vantage point: if your current point is too large, the entire column below you is guaranteed to be even larger—you can blast away that whole column forever by stepping left! If your current point is too small, the entire row to your left is guaranteed to be even smaller—you can blast away that entire row forever by stepping down! With every single footstep, an entire mountain ridge evaporates from the map.
Pitfall: The top-right corner is a saddle point: all elements to its left are smaller; all elements below it are greater.
Pitfall: Each comparison unconditionally eliminates either 1 entire column or 1 entire row.
Pitfall: Total steps cannot exceed M + N.
4-Phase Thought Process Model
Senior SWE thought process architecture for Saddleback 2D Matrix Elimination.
Pattern Recognition Signals
The 10-second spot
The matrix has sorted rows and sorted columns. Starting at gives no decision boundary because both axes increase. Identify as the saddle point.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Maintain the invariant that the candidate target must lie in matrix[r..M-1][0..c]. Any cell outside this bounding box is mathematically proven not to contain target.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Loop guard:
while r < m and c >= 0:Return immediately upon match:
return TrueExhaustion return:
return False
The 60-Second Interview Pitch
Say this out loud before you type a single line
In each iteration, either increments or decrements. can increment at most times, and can decrement at most times. The total iterations are strictly bounded by .
Standing at the top-right corner of a row-and-column sorted matrix turns search into an elimination walk that drops a whole row or column per comparison. If the current value exceeds the target, eliminate the entire column (col--); if smaller, eliminate the entire row (row++). Discards M + N cells in O(M + N) with zero memory.
Complexity & Mathematical Proof
O(M + N)
The pointer r starts at 0 and can increment at most M times before violating r < M. The pointer c starts at N - 1 and can decrement at most N times before violating c >= 0. In each step of the while loop, exactly one pointer moves. The total number of loop iterations is at most M + N. Each iteration performs one array lookup and two integer comparisons (O(1)). Therefore, the total time complexity is strictly O(M + N).
O(1)
The algorithm uses exactly two integer variables (r and c) to store the current matrix coordinates. No auxiliary arrays, sets, or recursive call stack frames are allocated. Auxiliary space complexity is strictly O(1).
The pointer r starts at 0 and can increment at most M times before violating r < M. The pointer c starts at N - 1 and can decrement at most N times before violating c >= 0. In each step of the while loop, exactly one pointer moves. The total number of loop iterations is at most M + N. Each iteration performs one array lookup and two integer comparisons (O(1)). Therefore, the total time complexity is strictly O(M + N).
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Identifies why (0, 0) and (M-1, N-1) fail to provide a greedy decision rule. • Chooses either (0, N-1) or (M-1, 0) without hesitation and clearly states the elimination invariant. • Proves the maximum step count is M + N without hand-waving. • Analyzes memory cache locality: notes that column decrements (c -= 1) remain within the same row cache line, whereas row increments (r += 1) jump by stride N.
m == matrix.length. n == matrix[i].length. 1 <= n, m <= 300. -109 <= matrix[i][j] <= 109. All the integers in each row are sorted in ascending order. All the integers in each column are sorted in ascending order. -109 <= target <= 109
In spatial GIS indexing (e.g. Google Maps raster elevation grids, geohash bounding boxes), saddleback elimination quickly finds bounding contours across pre-sorted tile pyramids.
Core Algorithmic State Invariants
The search interval represents the candidate domain. Mid-point calculation and range shifts must shrink this space strictly monotonically without skipping candidate solutions.
The predicate function checks monotonic truth. If true, the candidate is a viable bound, allowing pruning of the discarded partition.
Convergence is guaranteed when the candidate interval reduces to size 1, returning the recorded boundary index without off-by-one errors.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| row, col = 0, len(matrix[0]) - 1 | row, col = 0, len(matrix[0]) - 1 | Saddle point selection: starting at the top-right corner allows moving left to decrease values and moving down to increase values. |
| if val > target: col -= 1 | if val > target:
col -= 1 | Since column elements increase downwards, matrix[row..m-1][col] > target. Safely eliminates the entire column in O(1) decision time. |
| else: row += 1 | else:
row += 1 | Since row elements increase rightwards, matrix[row][0..col] < target. Safely eliminates the entire row in O(1) decision time. |