1547. The Boundary Row by Row

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. Given a bar x, print, for each row in order, how many of its entries are STRICTLY less than x.

The whole answer must be produced in time proportional to R + C, not R log C.

1 3 5 7 9 x = 6 -> 3 2 1 0 2 4 6 8 10 5 7 9 11 13 8 10 12 14 16

1 2 3 4 x = 100 -> 4 4 4 every entry is below the bar 5 6 7 8 9 10 11 12

5 5 5 5 x = 5 -> 0 0 0 nothing is STRICTLY below 5 5 5 5 5 5 5 5 5

## What most people try first

A binary search per row. It is correct, it is O(R log C), and it uses the row promise only. At R = C = 1000 that is about 10^4 steps, which is fine, so the reason to do better is the structure rather than the clock: the column promise says the answers are RELATED, and a method that searches each row independently never notices.

## The counts never increase down the rows

Let f(r) be the answer for row r. Because every column is non-decreasing, grid[r+1][j] >= grid[r][j] for every j. So any entry of row r+1 that is below x sits above an entry of row r that is also below x, which gives f(r+1) <= f(r). The sequence of answers is non-increasing, and it starts at most C and ends at least 0.

## One pointer that only moves left

j = C for r in 0 .. R-1: while j > 0 and grid[r][j-1] >= x: j = j - 1 answer[r] = j

j is the count for the current row: everything in columns 0 .. j-1 is below x and everything from column j on is not.

## Why the pointer is never moved back

Entering row r, j holds f(r-1), and f(r) <= f(r-1), so the correct value is at or to the LEFT of where the pointer already is. The inner loop only decreases j, and it stops as soon as grid[r][j-1] < x, which by the row order means every entry further left is below x too. So j is exactly f(r).

The pointer starts at C and never increases, so the inner loop runs at most C times over the WHOLE grid, not per row. Together with the R iterations of the outer loop that is O(R + C).

## The comparison that decides the answer

The count is of entries STRICTLY below x. The all-fives grid with x = 5 answers 0 for every row; using <= would answer 4. Every other declared test agrees under both comparisons, which is why that one is there.

## The two ends

x above everything gives C on every row and the pointer never moves. x below everything gives 0 on every row, and the pointer walks all the way left during the FIRST row and then never moves again, which is the case that shows the total work is bounded by C rather than by R C.

## Overflow

Counts are at most C, which is 1000. Values reach 10^9, which fits in a signed 32 bit integer since the limit is 2147483647. Nothing is added.

## Cost

O(R + C) after reading the grid, and O(R) for the answer itself. Problem 1546 counts cells in a value band over the whole grid with the same kind of walk; this one reports the boundary position per row rather than a single total.

Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - `-10^9 ≤ x ≤ 10^9` - `-10^9 ≤ each value ≤ 10^9` - every row is non-decreasing left to right and every column is non-decreasing top to bottom - the whole answer must cost `O(R + C)`, not `O(R log C)` - `R` and `C` are independent; the grid need not be square