Show problems as
Classic problem #1944HardArrayStackMonotonic Stack

Number of Visible People in a Queue

Real-world version: Sightlines Down the Mast Row
Tracked in this browser only
Read Number of Visible People in a Queue on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A survey line carries radio masts, listed left to right in masts by height. No two masts are the same height.

An engineer standing on top of mast i faces the right-hand end of the line. For a mast j further along, that is with j > i, the engineer can see mast j when every mast standing between them is shorter than mast i and shorter than mast j. Nothing else blocks the view.

Return an array whose entry i is the number of masts to the right of mast i that the engineer on mast i can see.

Examples

Example 1

Input
masts = [7, 3, 5, 2, 4]
Output
[2, 1, 2, 1, 0]

From mast 0, of height 7, the masts of height 3 and 5 are visible, while the ones of height 2 and 4 are hidden behind the mast of height 5. From mast 2, of height 5, the masts of height 2 and 4 are both visible.

Example 2

Input
masts = [4, 3, 2, 1]
Output
[1, 1, 1, 0]

The heights fall away to the right, so from any mast every mast beyond it is visible: 3 from the first, then 2, then 1, then none.

Example 3

Input
masts = [1, 2, 3, 4]
Output
[1, 1, 1, 0]

From mast 0 the mast of height 2 is visible; the mast of height 3 is not, because the mast of height 2 between them is not shorter than mast 0. The same holds along the line.

Constraints

  • n == masts.length
  • 1 <= n <= 10^5
  • 1 <= masts[i] <= 10^5
  • The heights are all different.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def visible_masts(masts: list[int]) -> list[int]:
Java
public int[] visibleMasts(int[] masts)

More on the same topics