779. The kth Smallest When Only the Rows Are Sorted

An R by C grid is given. Every ROW is in non-decreasing order. Nothing at all is promised about the columns. Print the kth smallest of the R * C values, counting duplicates separately and counting from 1.

``` grid 1 5 9 2 6 10 3 7 11

k = 1 -> 1 k = 5 -> 6 k = 9 -> 11 ```

``` grid 1 1 1 1 1 1

k = 4 -> 1 every value is the same, so every k answers 1 ```

``` grid -9 -9 -3 -3 -8 -8 -8 100

k = 5 -> -8 sorted: -9 -9 -8 -8 -8 -3 -3 100 ```

## Flattening is the obvious move and it is the wrong one

R and C reach 1000, so the grid holds 10^6 values. Copying them out and sorting costs O(R C log(R C)) time and O(R C) extra memory, and it throws away the one fact the input gives you for free: each row is already ordered.

## Count instead of sort

Guess a value x. How many grid entries are at most x? Each row is sorted, so a binary search inside that row answers it in O(log C), and the whole grid answers in O(R log C):

count(x) = sum over rows of (number of entries in that row <= x)

## Why the count is monotone in x

Raising x can only let more entries qualify, never fewer, because "at most x" is implied by "at most x - 1". So count is non-decreasing. That is the whole justification, and it never depends on the columns being sorted, which is why this problem works where #780's faster staircase counter would be wrong.

## Why the answer is a value that really occurs

Search for the SMALLEST x with count(x) >= k. At the stopping point count(x) >= k and count(x - 1) < k, so at least one grid entry lies strictly above x - 1 and at most x. Entries are integers, so that entry equals x. The loop never looked at a stored value and still cannot return one that is not there.

Search instead for the smallest x with count(x) > k, or stop as soon as count(x) == k, and this guarantee is gone. With the grid 1 1 1 / 1 1 1 and k = 4, an == k test never fires at all, because the count jumps from 0 to 6.

## The bounds

lo is the smallest first-column entry, hi is the largest last-column entry. Both are found in O(R) because each row is sorted. Starting from -10^9 and 10^9 also works and costs one extra step or two.

## The boundary that breaks a careless implementation

Values may be negative, and in C, C++ and Java integer division truncates TOWARDS ZERO, so (-3 + 2) / 2 is 0 rather than -1 and the search can stop moving. Write mid = lo + (hi - lo) / 2, where hi - lo is positive whenever the loop is still running and the truncation therefore rounds the way the search needs.

The grid -9 -9 -3 -3 / -8 -8 -8 100 with k = 5 is the case that proves it, and it is in the tests. A (lo + hi) / 2 search on it walks down to lo = -9, hi = -8, where the midpoint is -17 / 2, which truncates to -8 rather than -9. The count at -8 is 5, so hi is set to -8, which is where it already was. The loop never terminates.

## Relationship with problem 628

628 asks this same question, the kth smallest of sorted sequences taken together with duplicates counted separately, and answers it by walking the merge: k steps, each one producing the next value in order. With two lists that walk is a pair of pointers and nothing else.

Here there are R sorted rows rather than two, and k reaches R * C, so the walk costs a step per value and needs a heap to decide which row moves next. The escape is to give up on order altogether. This search never produces a single value in sequence; it only counts how many entries are at most x, and reads the answer off where that count crosses k.

## Where the 32-bit ceiling actually is

The widest the search range can be is -10^9 to 10^9, so hi - lo reaches 2000000000 and lo + hi reaches the same magnitude. A signed integer held in 32 bits stops at 2147483647, so both sit inside it, and the count is capped at R * C, which is 10^6. No part of this problem needs a wider type.

Say that plainly, because the usual reason given for avoiding (lo + hi) / 2, an overflowing sum, is not the reason here. The reason here is the truncation, and it is enough on its own.

## Cost

Time O(R log C log(range)). Space O(1) beyond the grid.

Constraints - `1 ≤ R, C ≤ 1000` - `1 ≤ k ≤ R * C` - `-10^9 ≤ each value ≤ 10^9` - every row is non-decreasing