Search 2D Matrix II
Mahabharata — The Staircase Descent — Navigating a Partially Sorted Grid
ऊपर-दाएं कोने से शुरू — बड़ा है तो नीचे जाओ, छोटा है तो बाएं। O(m+n) में उत्तर — सीधी सीढ़ी जैसे॥
*Start from the top-right corner — if larger go down, if smaller go left. O(m+n) answer — like a straight staircase.*
The Story
A matrix where each row is sorted left-to-right AND each column is sorted top-to-bottom. Find target.
For `matrix=[[1,4,7,11],[2,5,8,12],[3,6,9,16],[10,13,14,17]]`, target=5: return true.
**Unlike bs-19, we can't flatten to 1D.** The first element of row[i+1] is NOT necessarily larger than the last of row[i].
**The Staircase Search — O(m+n):** Start at the top-right corner (row=0, col=n-1): - If matrix[r][c] == target → found! - If matrix[r][c] > target → move LEFT (current column too large; all elements below also too large) - If matrix[r][c] < target → move DOWN (current row all smaller; current row is exhausted for target)
Each step eliminates either one row or one column. At most m+n steps.
Trace target=5: - (0,3): 11>5 → left (0,2) - (0,2): 7>5 → left (0,1) - (0,1): 4<5 → down (1,1) - (1,1): 5==5 → return true ✓
**Why top-right (not top-left or bottom-right)?** Top-right: row increases → values increase; column decreases → values decrease. Exactly one elimination direction per comparison. Top-left: both directions increase → ambiguous. Bottom-right: both decrease → ambiguous.
The Full Matrix Scan
Check every cell. O(mn).
public boolean searchMatrixBruteForce(int[][] matrix, int target) {
for (int[] row : matrix)
for (int v : row)
if (v == target) return true;
return false;
}The Top-Right Staircase Wisdom
public boolean searchMatrix(int[][] matrix, int target) {
int r = 0, c = matrix[0].length - 1;
while (r < matrix.length && c >= 0) {
if (matrix[r][c] == target) return true;
if (matrix[r][c] > target) c--; // Too large: move left
else r++; // Too small: move down
}
return false;
}Step-by-Step Walkthrough
1×1 matrix [[5]], target=5 r=0,c=0. matrix[0][0]=5==5 → true ✅
Deep Insight
**Why this works in O(m+n)?** Starting at top-right: - Each 'move left' eliminates the entire column to the right of current position (all rows below would have even larger values there) - Each 'move down' eliminates the entire current row (all columns to the left are smaller)
At most n left moves + m down moves = O(m+n).
**bs-19 vs bs-20 comparison:** | | bs-19 | bs-20 | |---|---|---| | Sorting guarantee | Rows sorted + row continuity | Rows & columns sorted | | Approach | O(log mn) binary search | O(m+n) staircase | | Flatten to 1D? | Yes | No |
bs-19 has STRONGER guarantee → faster algorithm. bs-20 has weaker guarantee → different approach needed.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(mn) | O(1) | Scan all cells |
| Optimal | O(m+n) | O(1) | Staircase: at most m+n steps eliminating one row/column each |
Pattern Recognition
✅ Row-sorted AND column-sorted matrix ✅ Start at top-right (0, n-1) ✅ too large→left; too small→down ✅ O(m+n) — not binary search but related principle **LeetCode Trigger Phrases:** → "search a 2D matrix II" (only row+col sorted, not fully) → Staircase search from corner → Partially sorted 2D grid search
Bhagavad Gita 13.29
प्रकृत्यैव च कर्माणि क्रियमाणानि सर्वशः। यः पश्यति तथात्मानमकर्तारं स पश्यति॥
One who sees that all actions are performed by Nature alone, and that the Self does not act — that one truly sees.
Connection: The staircase search moves with Nature's flow — when the value is too large, it naturally moves left; when too small, naturally downward. There is no backtracking, no re-examination — each step follows the matrix's inherent structure. Like the sage who moves with Nature's forces without personal agenda, the algorithm follows the sorting properties without imposing extra computation, reaching the answer through pure structural alignment.