Who Is Visible to the Right

Hard

There are n towers along a street from left to right, with heights given in heights; all heights are distinct. Tower i can see tower j if i < j and every tower strictly between them is lower than both: min(heights[i], heights[j]) > max(heights[i+1..j-1]). Adjacent towers always see each other. Return an array of length n whose entry i is the number of towers to the right that tower i can see. Checking all pairs is O(n²); an O(n) solution exists.

Example 1

heights=[4, 2, 3, 1, 5] → [3, 1, 2, 1, 0]

Tower 0 sees towers 1, 2 and 4 (tower 3 is hidden by tower 2). Tower 1 sees only 2, tower 2 sees 3 and 4, tower 3 sees 4, and the last one sees nothing.

Example 2

heights=[1, 2, 3] → [1, 1, 0]

Each tower sees only its neighbour, which is taller and blocks everything behind it.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ heights[i] ≤ 10⁵
All heights are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Array Monotonic Stack

Similar problems

Water Between Walls Hard Biggest Rectangle Under the Skyline Hard Biggest Solid Panel Block Hard Largest Number From Two Rows Hard Sorting Batches With Repeats Hard

Input

heights=[4, 2, 3, 1, 5]

Expected

[3, 1, 2, 1, 0]

Run checks the first 3 tests in your browser. Submit checks all 99 tests on the server, hidden ones included.