A garden crew maintains a straight row of n trimmed hedges, each with an integer height. Every night, the crew re-levels the row using one simple rule applied simultaneously to every interior hedge (every hedge except the first and the last), based on that hedge's two immediate neighbors from before that night's work began: if a hedge is strictly taller than both of its neighbors, it is trimmed down by exactly 1; if a hedge is strictly shorter than both of its neighbors, it is built up by exactly 1; otherwise it is left alone. The two end hedges are never touched. This nightly pass repeats, night after night, until a night passes with no change at all to any hedge. Report the row's final, stable heights.
Print the n final heights, space-separated on one line, once the row has stabilized.
Example 1
Input
4 6 2 3 4
Expected
6 3 3 4
Explanation
Endpoints 6 and 4 never change. Night 1 (using the original heights 6,2,3,4): hedge 2 (height 2) is strictly shorter than both neighbors 6 and 3, so it rises to 3; hedge 3 (height 3) has neighbors 2 and 4 and is neither strictly greater nor strictly less than both, so it is unchanged. The row becomes 6,3,3,4. Night 2 (using 6,3,3,4): hedge 2's neighbors are now 6 and 3 (equal to it), and hedge 3's neighbors are 3 (equal) and 4, so neither qualifies as a strict peak or valley and nothing changes. The row has stabilized at 6 3 3 4.
Example 2
Input
3 1 5 2
Expected
1 2 2
Explanation
Endpoints 1 and 2 never change. The middle hedge starts at 5, strictly taller than both neighbors, so it is trimmed by 1 each night: 5 -> 4 -> 3 -> 2. Once it reaches 2 its neighbors are 1 and 2, and 2 is not strictly greater than both (it equals the right neighbor), so trimming stops. The final row is 1 2 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →