0474MediumArrayStackMonotonic Stack

Silos With a Clear Line to the River

Tracked in this browser only

Trains the technique from

LeetCode 1762Buildings With an Ocean View

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Grain silos stand in one straight line along a rail spur. heights[i] is the height of the silo at index i, and the indices run from the far end of the spur towards the river, so the river lies just past the last silo in the list.

A silo has a clear line to the river when every silo standing between it and the river is strictly shorter than it is. A silo of exactly the same height blocks the line, and the silo closest to the river has nothing in front of it at all.

Return the indices of all silos with a clear line to the river, in increasing order.

Examples

Example 1

Input: heights = [3, 8, 8, 2, 5, 5, 1]
Output: [2, 5, 6]

Indices 2, 5 and 6 each stand taller than everything left between them and the river. Index 4 is beaten by the equally tall silo at index 5, so it is left out.

Example 2

Input: heights = [6, 6, 6]
Output: [2]

All three silos match in height, so only the one nearest the river keeps its line.

Example 3

Input: heights = [11, 4, 9, 9, 2]
Output: [0, 3, 4]

Index 0 towers over the rest of the row, index 3 only has the short silo at index 4 in front of it, and index 4 is nearest the river.

Constraints

1 <= heights.length <= 10^5
1 <= heights[i] <= 10^9

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def silos_with_river_view(heights: list[int]) -> list[int]:

Java

public int[] silosWithRiverView(int[] heights)

The intended approach

Time O(n), each index pushed and popped at most onceSpace O(n) for the stack, which is returned as the answer

Sweep the row from the far end towards the river holding a stack of the silos that still have a clear line. A newly reached silo blocks every silo already on the stack whose height does not exceed it, so pop those off before pushing the new index. Because the sweep runs in index order and each index is pushed once, the stack that survives to the end already lists the answer in increasing order.

Pythonentry point: silos_with_river_view

def silos_with_river_view(heights):
    # A silo keeps its view only while nothing at or above its height turns up later,
    # so hold the current survivors on a stack and evict any the new silo blocks.
    # time O(n) amortised, space O(n) for the stack, which is the answer itself
    keeping = []
    for i in range(len(heights)):
        tall = heights[i]
        while keeping and heights[keeping[-1]] <= tall:
            keeping.pop()
        keeping.append(i)
    return keeping

The obvious version

Test every silo on its own by walking the whole stretch between it and the river and looking for anything at least as tall. Collect the indices that survive their walk.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_silos_with_river_view(heights):
    picked = []
    for i in range(len(heights)):
        clear = True
        for j in range(i + 1, len(heights)):
            if heights[j] >= heights[i]:
                clear = False
                break
        if clear:
            picked.append(i)
    return picked

How this problem was checked

Reference solution executed against 9 test cases — 9 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in