Solar Mast Sightlines
Count array pairs with no intervening value above the smaller endpoint
A solar farm has a straight row of monitoring masts. The array heights gives their heights in row order.
Two different masts can establish a direct monitoring link if every mast strictly between them is no taller than the shorter of the two endpoint masts. An intermediate mast of exactly that height does not block the link. Adjacent masts can always establish a link.
Return the total number of pairs of masts that can establish a link. Each pair is counted once, regardless of direction. If there are fewer than two masts, return 0.
Examples
Example 1
Input: heights = [6,2,2,5] Output: 6
For heights [6, 2, 2, 5], all three adjacent pairs qualify. The first and third masts also qualify because the intervening height is 2, and the first and fourth qualify because both intervening heights are at most 5. The second and fourth do not qualify because their intervening mast is taller than the shorter endpoint.
Example 2
Input: heights = [4,4,4,4] Output: 6
All masts have the same height, so every pair qualifies, including pairs with other masts between them.
Example 3
Input: heights = [2,7,3] Output: 2
The two adjacent pairs qualify. The first and last masts cannot link because the middle mast is taller than both endpoints.
Constraints
- 0 <= heights.length <= 8000
- 1 <= heights[i] <= 1000
The intended solution takes O(n) time and O(n) auxiliary space. Equal-height groups must retain their multiplicities.
Hints
Show hint 1Hint 1
Scan from left to right. Which earlier masts become permanently hidden from future masts when a taller mast arrives?
Show hint 2Hint 2
Maintain decreasing heights on a stack and group equal heights together. A new mast can see all members of each shorter group it removes, all members of an equal-height group, and at most one mast from the next taller group.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would the algorithm change if an intermediate mast of equal height blocked a link?
- Can you process heights arriving as a stream and report the cumulative pair count after each arrival?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem