Search 2D Matrix (Young Tableau): Finding 5 & 20

Imagine you are handed a $5\times 5$ grid of integers where every row is sorted from left to right, and every column is sorted from top to bottom. This structure is often called a Young tableau or a sorted 2D matrix. Your mission is simple: determine if the number 5 is hiding inside the grid, and verify whether the number 20 is completely absent.

Here is our locked working example matrix:

If you treat this grid like a flat, one-dimensional list and scan every single cell from top-left to bottom-right, you will find 5 at row index 1, column index 1, and you will eventually exhaust all 25 elements to confirm 20 is missing. But what happens when the matrix scales to $1000\times 1000$? A brute-force linear search inspects every element, costing $O(m\times n)$ time and completely ignoring the strict ordering guarantees built into the rows and columns.

Even a standard binary search on every individual row takes $O(m\log n)$ time, which misses the cross-row relationships. We need a strategy that actively eliminates entire rows or columns in a single comparison. Without a deliberate geometric entry point, we waste time walking blindly through values that could easily be skipped.

Try this: Given matrix: 5x5. Search targets: 5 (present) and 20 (absent).

This specific corner acts as a decision pivot. It gives us a binary choice at every step: if our target is smaller than the current element, all elements to the right and below are larger, so we can safely eliminate the entire column by moving left. If our target is larger, all elements above and to the left are smaller, so we can safely eliminate the entire row by moving down. We never start at the top-left corner 1, because from 1, both moving right (4) and moving down (2) lead to larger numbers—leaving us with no monotonic way to discard data.

To formalize this staircase navigation through our locked matrix, our state pointer $(r,c)$ starts at row $r=0$ and column $c=4$ (the value 15). At each iteration, we compare $\text{matrix}[r][c]$ against our target. For target 5, since $5<15$, we decrement $c$ to move left to 11. For target 20, since $20>15$, we increment $r$ to move down to 19. Every single comparison drops either one entire row or one entire column from consideration.

Try this: Given the locked 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]]
Explain why starting the search pointer at matrix[0][4] allows us to eliminate a whole column when target < matrix[0][4], whereas starting at matrix[0][0] provides no such monotonic guarantee.

To prove why our search for 5 and 20 runs in $O(m+n)$ time, we need precise mathematical notation for our $m\times n$ matrix and its sorted properties. Let the matrix be denoted as $A\in {\mathbb{R}}^{m\times n}$, where $m$ is the number of rows and $n$ is the number of columns. In our locked working example, $m=5$ and $n=5$, and the matrix is explicitly given by:

Each element is represented by $A[r][c]$, where $r\in \{0,1,\dots ,m-1\}$ is the row index and $c\in \{0,1,\dots ,n-1\}$ is the column index. The Young tableau properties guarantee two strict inequalities for any valid coordinates:

1. Row-sorted order: $A[r][c]<A[r][c+1]$ for all valid $r$ and $c<n-1$.
2. Column-sorted order: $A[r][c]<A[r+1][c]$ for all valid $c$ and $r<m-1$.

Our pointer pair $(r,c)$ starts at the top-right corner, meaning $r_0=0$ and $c_0=n-1=4$. For our target $t$, the state transition at any step is governed by a strict trichotomy:

- If $A[r][c]=t$, the search terminates successfully with a match.
- If $A[r][c]>t$, the current value is strictly greater than the target. Because row $r$ is sorted in ascending order to the right, every element to the right of $c$ is also greater than $t$. Thus, we decrement the column index: $c_{next}=c-1$.
- If $A[r][c]<t$, the current value is strictly smaller than the target. Because column $c$ is sorted in ascending order downward, every element above or at row $r$ in this column is also smaller than or equal to $A[r][c]$. Thus, we increment the row index: $r_{next}=r+1$.

Try this: Given A[0][4] = 15 and target = 20, state whether r or c updates and write the resulting inequality for the next pointer state.

Let us execute our staircase search on the locked $5\times 5$ matrix:

Given: $m=5,n=5$, $\text{target}=5$, initial pointer at top-right $(r=0,c=4)$.

Steps:
1. Check $\text{matrix}[0][4]=15$. Since $5<15$, we discard column 4 by decrementing $c$ to 3. Current pointer: $(0,3)$, value = 11.
2. Check $\text{matrix}[0][3]=11$. Since $5<11$, we decrement $c$ to 2. Current pointer: $(0,2)$, value = 7.
3. Check $\text{matrix}[0][2]=7$. Since $5<7$, we decrement $c$ to 1. Current pointer: $(0,1)$, value = 4.
4. Check $\text{matrix}[0][1]=4$. Since $5>4$, we discard row 0 by incrementing $r$ to 1. Current pointer: $(1,1)$, value = 5.
5. Check $\text{matrix}[1][1]=5$. The current value matches our target $5$.

Result: Found at $(1,1)$, returning true.

Given: $m=5,n=5$, $\text{target}=20$, initial pointer at top-right $(r=0,c=4)$.

Steps:
1. Start at $(0,4)$, value = 15. $20>15$ $\implies r $+=1\to$ (1, 4) \), value = 19.
2. At $(1,4)$, value = 19. $20>19$ $\implies r $+=1\to$ (2, 4) \), value = 22.
3. At $(2,4)$, value = 22. $20<22$ $\implies c $-=1\to$ (2, 3) \), value = 16.
4. At $(2,3)$, value = 16. $20>16$ $\implies r $+=1\to$ (3, 3) \), value = 17.
5. At $(3,3)$, value = 17. $20>17$ $\implies r $+=1\to$ (4, 3) \), value = 26.
6. At $(4,3)$, value = 26. $20<26$ $\implies c $-=1\to$ (4, 2) \), value = 23.
7. At $(4,2)$, value = 23. $20<23$ $\implies c $-=1\to$ (4, 1) \), value = 21.
8. At $(4,1)$, value = 21. $20<21$ $\implies c $-=1\to$ (4, 0) \), value = 18.
9. At $(4,0)$, value = 18. $20>18$ $\implies r $+=1\to$ (5, 0) \), which violates $r<m$.

Result: Pointer falls out of bounds without finding 20, returning false.

Try this: Trace the algorithm manually for target = 13 starting from (0, 4). List the sequence of coordinates and values visited until found.

Your task is to trace the execution steps when searching for the target value 13. Start at the top-right corner element 15 at coordinates $(r=0,c=4)$, and apply the staircase comparison rules: if the current value equals 13, return true; if 13 is less than the current value, decrement the column index $c$; if 13 is greater, increment the row index $r$. Write down the sequence of visited cells until you find 13 or exceed the matrix bounds.

Try this: Given the 5x5 matrix and starting position r=0, c=4 (value 15):

Having mastered the top-right staircase search on our locked $5\times 5$ matrix to locate 5 and 20 in $mathcalO(m+n)$ time, we can now extract the underlying structural pattern. The core trick—starting at a corner where movement in one direction strictly increases values and movement in the orthogonal direction strictly decreases values—is not unique to strict Young tableaux. It applies to any matrix where rows and columns are individually sorted in the same monotonic direction.

Suppose you encounter a variant grid where each row is sorted left-to-right and each column is sorted top-to-bottom, but adjacent rows do not strictly interleave their values like a strict Young tableau. Does the top-right corner (matrix[0][n-1]) still work as our pivot? Yes! Moving left decreases values, and moving down increases values, preserving the exact same elimination invariant we used for 5 and 20.

However, what happens if we attempt to apply this same staircase logic to a matrix where rows are sorted left-to-right and columns are sorted bottom-to-top instead? The monotonicity breaks our pivot logic: moving down now decreases values rather than increasing them. Recognizing these structural symmetries allows you to re-orient your starting corner—choosing bottom-left or top-right—to match the matrix's specific gradient.

By abstracting the staircase search from raw indices to a gradient-following agent, you can solve related search problems in compressed quad-trees, sorted sub-grid lookups, and multidimensional threshold queries without rewriting your core traversal logic.