A border-security agency maintains a straight line of n watchtowers along a stretch of frontier fence, numbered 0 (westernmost) through n-1 (easternmost). Tower i currently has a recorded height, height[i]. For an upcoming line-of-sight audit, the agency wants each tower's recorded value replaced by the tallest height among all towers strictly to its east -- that is, among towers with a larger index. The easternmost tower has no tower to its east, so its updated value must become -1.
Print n space-separated integers: the updated heights, in tower order.
Example 1
Input
5 5 4 3 2 1
Expected
4 3 2 1 -1
Explanation
Heights are strictly decreasing: 5 4 3 2 1. For tower 0 the tallest tower east of it is height 4 (tower 1); for tower 1 it's height 3; for tower 2 it's height 2; for tower 3 it's height 1 (tower 4); tower 4 is the easternmost tower and becomes -1. Result: 4 3 2 1 -1.
Example 2
Input
4 2 7 3 7
Expected
7 7 7 -1
Explanation
Heights are 2 7 3 7. East of tower 0 the towers are [7, 3, 7], tallest is 7. East of tower 1 the towers are [3, 7], tallest is 7. East of tower 2 the only tower is [7], so 7. Tower 3 is the easternmost and becomes -1. Result: 7 7 7 -1.
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 →