780. The kth Smallest in a Doubly Sorted Grid
An R by C grid is given in which every ROW is non-decreasing left to right AND every
COLUMN is non-decreasing top to bottom. Print the kth smallest of the R * C values, counting
duplicates separately and counting from 1.
``` grid 1 5 9 10 11 13 12 13 15
k = 1 -> 1 k = 8 -> 13 k = 9 -> 15 ```
``` grid 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7
k = 7 -> 4 the value 4 occupies four cells ```
``` grid -10 -10 -4 0 0 -10 -3 0 0 1
k = 6 -> 0 ```
## What the extra promise buys
Problem 779 asks the same question with only the ROWS sorted, and counts with one binary search
per row for O(R log C) per guess. Here the columns are sorted too, and that turns the counting
into a single walk of length R + C.
Read that sentence as the lesson: the search skeleton is unchanged, and a stronger structural promise makes only the COUNTER cheaper.
## The staircase walk
Stand at the bottom-left cell and move:
r = R - 1, c = 0, count = 0
while r >= 0 and c < C:
if grid[r][c] <= x:
count += r + 1 the whole column above this cell also qualifies
c += 1
else:
r -= 1
When grid[r][c] <= x, every cell above it in column c is at most grid[r][c], because the
column rises downward. So r + 1 cells qualify in one step and column c is finished. When it
is too big, every cell below it in that column is too big as well, so the row can be abandoned.
Each step consumes a row or a column, so the walk takes at most R + C steps.
Running this walk starting from the TOP-LEFT corner is the classic wrong version: from there neither branch can eliminate a whole line, and the walk either misses cells or revisits them.
## Why the count is monotone, and why the answer occurs
count(x) is the number of cells at most x, which cannot shrink when x grows. Search for
the smallest x with count(x) >= k. At the stop, count(x - 1) < k <= count(x), so some cell
sits in (x - 1, x], and cells are integers, so a cell equals x.
The grid 1 1 1 / 1 1 1 / 1 1 1 is the case worth checking by hand: count is 0 for every
x < 1 and 9 for every x >= 1, so any predicate that hunts for count(x) == k with k = 5
never fires, while the lower-bound search lands on 1 immediately.
## The bounds
The smallest value is grid[0][0] and the largest is grid[R-1][C-1], both guaranteed by the
double ordering. That is tighter than #779 can manage and costs nothing to obtain.
## The boundary that breaks a careless implementation
r reaching -1 and c reaching C are both normal loop exits, not errors. Writing the walk
as while (true) with the bounds checked only inside one branch reads past the edge of the grid
on any input where the guess is above or below everything, which is exactly what the first and
last iterations of the search do.
## Where the 32-bit ceiling actually is
Values span -10^9 to 10^9, so hi - lo reaches 2000000000 and lo + hi reaches the same
magnitude, both inside the 2147483647 a signed integer held in 32 bits reaches. The count is
capped at R * C, which is 10^6. No part of this problem needs a wider type.
Compute mid = lo + (hi - lo) / 2 all the same, for a reason about the sign rather than the
width: integer division in C, C++ and Java truncates TOWARDS ZERO, so (lo + hi) / 2 rounds the
wrong way once the range is entirely negative and the search can stop moving. Problem 779 carries
a grid that sends the (lo + hi) / 2 form into an infinite loop. Nothing in the tests here does,
which is a reason to write the safe form rather than a reason to relax.
## Cost
Time O((R + C) log(range)). Space O(1) beyond the grid.
Constraints - `1 ≤ R, C ≤ 1000` - `1 ≤ k ≤ R * C` - `-10^9 ≤ each value ≤ 10^9` - rows and columns are both non-decreasing
Input
The first line contains three integers R, C and k.
Each of the next R lines contains C integers. Rows are non-decreasing left to right and columns are non-decreasing top to bottom.
Output
Print a single integer: the kth smallest value in the whole grid.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.