Pour Water I
heights[i] is the terrain height at index i. volume units of water are dropped at index k, one unit at a time. Each unit:
- moves left if it can reach a strictly lower resting spot without ever climbing;
- otherwise moves right under the same rule;
- otherwise stays at
k.
A unit settles on the lowest reachable spot (the first such spot in its direction of travel) and raises that column by one. Return the final heights.
pourWater([2,1,1,2,1,2,2], 4, 3) -> [2,2,2,3,2,2,2]
Hints
Hint 1
Simulate each unit: walk left while the next cell is not higher, remembering the lowest cell seen; if that lowest cell is lower than k, drop the water there. Otherwise repeat to the right. Otherwise it stays at k.
Hint 2
Walking continues over flat ground (the next column is not higher), but a unit only lands on a strictly lower column. Update the lowest column only on a strict improvement, so ties keep the column closest to k.