skip to content

In a row- and column-sorted grid, why does starting at the top-right corner discard a row or column?

level: middleimportance: must knowfreq 65%

answer

  1. which corner makes one comparison decisive?
  2. extremal in both available directions
  3. largest in its row, smallest in its column
  4. each step retires a whole line
  5. top-left is minimum of both, so useless

basics

~20 s

The top-right cell is the largest in its row and smallest in its column, so one comparison rules out a whole line: too big drops the column, too small drops the row. That bounds the walk at m + n steps.

solid answer

~50 s

Entering at the top-right of a grid whose rows increase rightward and columns increase downward puts you on a cell that is simultaneously the **maximum of its row** and the **minimum of its remaining column**. That double role is what makes one comparison decisive. If the cell exceeds the target, every entry below it in that column is larger still, so the whole column is eliminated — step left. If it is less than the target, every entry to its left in that row is smaller still, so the whole row is eliminated — step down. Each step retires one full line, so the walk touches at most m + n − 1 cells: O(m+n). The top-**left** corner is the minimum of both its row and its column, so "too small" leaves two open directions and eliminates nothing. Bottom-left works for the mirrored reason.

code

pseudocode · 10 lines
pseudocode
r = 0
c = cols - 1
while r < rows and c >= 0:
    v = grid[r][c]
    if v == target: return (r, c)
    if v > target:
        c = c - 1      // whole column c ruled out
    else:
        r = r + 1      // whole row r ruled out
return NOT_FOUND

go deeper

for a junior

Recall that on a grid sorted along rows and along columns you enter at the top-right, step left when the cell is too large and down when it is too small, and that the walk costs about m + n steps.

for a middle

Explain the decisive-corner property — largest in its row, smallest in its column — and state the invariant that the target, if present, stays inside the live sub-rectangle. Be able to trace an absent value to termination.

for a senior

Derive which corners are usable rather than reciting one, name the diagonal-step and loop-guard bugs, and be clear that O(m+n) is inherent to what the weaker ordering guarantee provides, not a missed optimisation.

for a principal

Own the argument that the achievable bound follows from the ordering contract the data offers. Be ready to weigh strengthening that contract against living with linear-in-perimeter reads across a fleet.

## The property that makes a corner special Take a sales grid where rows are quarters and columns are regions, and both axes have been ordered so that values climb left to right and top to bottom: ``` 2 9 14 21 5 11 18 26 8 15 23 34 12 19 30 41 ``` Notice what this grid is *not*: row 0 ends at 21 while row 1 starts at 5, so the reading-order sequence is not sorted and flattening it for a binary search would be wrong. Only the two axis guarantees hold. Now ask which cells make a decisive comparison. A cell is decisive when knowing its relation to the target eliminates an entire line without ambiguity, and that requires the cell to be **extremal in both directions you could move**. - **Top-right (0, n−1) = 21.** It is the largest entry in row 0 and the smallest entry in column 3. If 21 > target, every entry below 21 in column 3 is at least 21, so column 3 cannot contain the target — drop it, move left. If 21 < target, every entry left of 21 in row 0 is at most 21, so row 0 cannot contain the target — drop it, move down. Both branches eliminate a line. Decisive. - **Top-left (0, 0) = 2.** It is the minimum of its row *and* the minimum of its column. If 2 < target, the target could be anywhere to the right or anywhere below — two open directions and no elimination. The only informative branch is 2 > target, which ends the search immediately, and that happens at most once. Not decisive. - **Bottom-left (m−1, 0) = 12.** The minimum of its row and the maximum of its column: too large drops the row, too small drops the column. Decisive, mirrored. - **Bottom-right = 41.** The maximum of both. Symmetric to top-left, and equally useless. So two of the four corners work and two do not, and the reason is a property of the corner, not a convention. Being able to *derive* which corners work — rather than reciting "start top-right" — is the whole point of the question. ## Tracing it Searching the grid above for 18, entering at (0,3): | step | cell | value | vs target 18 | action | |---|---|---|---|---| | 1 | (0,3) | 21 | greater | column 3 eliminated, move left | | 2 | (0,2) | 14 | less | row 0 eliminated, move down | | 3 | (1,2) | 18 | equal | found | And for an absent value, 20: | step | cell | value | vs target 20 | action | |---|---|---|---|---| | 1 | (0,3) | 21 | greater | drop column 3 | | 2 | (0,2) | 14 | less | drop row 0 | | 3 | (1,2) | 18 | less | drop row 1 | | 4 | (2,2) | 23 | greater | drop column 2 | | 5 | (2,1) | 15 | less | drop row 2 | | 6 | (3,1) | 19 | less | drop row 3 | Row index now runs past the last row, the live region is empty, and the answer is "not found" after 6 probes — comfortably inside the bound of m + n − 1 = 7. ## The invariant, stated properly At every step the algorithm maintains: *if the target is present anywhere in the grid, it is present in the live sub-rectangle rows `r..m−1` by columns `0..c`.* Initially that rectangle is the whole grid, so the invariant holds. Each step removes either row `r` or column `c` after proving that line cannot hold the target, so the invariant survives. The loop ends when the rectangle is empty, and the invariant then says the target is absent. This is the same style of argument binary search uses; only the shape of the discarded region differs — a line instead of a half. ## Why the cost is O(m+n), not O(log mn) Each iteration retires exactly one row or one column, and there are m rows and n columns, so at most m + n − 1 iterations occur before the region empties. Extra space is O(1): two indices. The bound is *not* logarithmic, and it cannot be made logarithmic by cleverness at the same corner — the weaker guarantee simply carries less information than a total order does. A candidate who claims the corner walk is O(log mn) has confused the two grid shapes. A linear-looking bound is also better than it sounds: for a 1,000 x 1,000 grid, m + n is about 2,000 against 1,000,000 cells. It is a 500x reduction achieved with two integer indices and no auxiliary structure. ## The failure modes to name Starting at the top-left is the classic one — people reach for it because that is where reading begins. Another is moving diagonally: stepping both left *and* down in one iteration discards cells that were never ruled out, and the search misses targets. A third is forgetting the loop guard on both indices; the walk must stop when the row index passes the last row **or** the column index falls below zero, and checking only one produces an out-of-range probe on absent targets.

  • Which of the four corners can you start from, and why do the other two fail?
    Top-right and bottom-left work; top-left and bottom-right do not. A usable corner is extremal in opposite senses along its row and its column, so one comparison eliminates a line either way. Top-left is the minimum of both and bottom-right the maximum of both, so the informative branch just ends the search and the other branch leaves two open directions.
  • Can the corner walk be improved below O(m+n) on this grid shape?
    Not by this method — each comparison at the corner rules out one line, so m + n − 1 steps is its ceiling and its floor. Other strategies with different asymptotics exist for lopsided shapes, but they exploit the aspect ratio rather than making the corner walk itself faster, and none is uniformly better.
  • What goes wrong if the walk steps diagonally when the probed value misses?
    It skips cells that were never eliminated. A too-large probe only proves the column is dead, not the row, so moving down as well abandons live candidates in that row, and the search can report "not found" for a present value. Every step must retire exactly one line.
  • How do you handle duplicate values in the grid with this walk?
    The walk is unaffected for a membership query: equality returns the first match reached, and the elimination arguments never assumed distinctness. If you need every occurrence, the walk finds one and you must explore the neighbouring live region separately, since duplicates can straddle rows and columns.

Think of standing at the corner of a stadium where seat prices rise as you go right and as you go back. From the far-right of the front row you are at the priciest seat in your row and the cheapest in your column, so one glance at the price tells you to abandon an entire column or an entire row.

saying these in an interview costs you the question

  • Starts the walk at the top-left because reading starts there
  • Claims the corner walk runs in O(log mn)
  • Moves both left and down in a single step
  • Cannot say why the top-right cell is decisive
  • Checks only one index in the loop guard and probes out of range

context

resolving links…