Two Pointers
Carrying state on both sides
The unit's hardest idea: pointers that remember a running value, and a decision that depends on which side is settled.
A per-position quantity
So far the answer has been a single number found by comparing two ends. Now consider problems where every position contributes something, and its contribution depends on what lies on both sides of it.
The concrete version: given a row of column heights, how much water sits on top of the row after rain? The total is a sum over columns, and no column can be worked out by looking at itself.
Why it works
Work one column out by hand
Take the heights [4, 1, 3] and look only at the middle column. The tallest thing to its left is 4 and the tallest to its right is 3. Water rises until it spills over the lower of those two walls, so it settles at 3, and the column itself already occupies 1 of that. One unit sits on top.
Generalize from that single column rather than from the picture. What a column holds depends on exactly two numbers, the tallest wall on each side, and on nothing else about the rest of the row. Deriving that sentence is the whole first half of any problem in this family, and it is worth doing on paper before any code exists.
Key idea
Both of those numbers come from a running maximum
The tallest value to the left of every position can be produced in one pass, by carrying a running maximum and reading it before absorbing the current element. Run the same loop backwards for the other side.
This is the Unit 1 prefix-and-suffix shape applied to maxima instead of sums, and it is worth practicing on its own. Below, the same running maximum answers a different question: which posts are visible to someone standing at the left end.
Gotcha
The comparison comes before the update
Swap those two lines and running already includes the current post, so the comparison becomes height > height and nothing is ever visible. The order is not a style choice, it is what makes the running value mean strictly before this position.
Whenever a loop carries a running value, say out loud which positions it covers. Almost every off-by-one in this family is that sentence being false by one element.
Tip
Write the array version first
Two directional sweeps and a combining pass is already O(n) time. The only thing wrong with it is the O(n) space it spends on the two arrays.
In an interview that is a complete answer, and offering it before attempting anything cleverer is the right move. You can then say the arrays can be removed if space matters, which is the follow-up they are usually waiting for.
Why it works
Collapsing to two pointers
To drop the arrays, keep only the best-so-far from each end and walk inward. The subtle part is knowing when a column's answer is actually decided.
At any moment you know the tallest wall seen from the left and the tallest seen from the right. You do not know the true tallest on the far side of each pointer. But you do not need to: if the left running maximum is smaller than the right running maximum, then for the left column the smaller of the two bounds is definitely the left one, because the right bound can only get taller as you learn more.
So the column on the side with the smaller running maximum has a settled answer, and that is the side to process and advance. Watch which side that is as the two maxima grow.
Tip
Update the running maximum before you use it
If the running maximum on a side is brought up to include the current position before that position's contribution is worked out, the contribution can never come out negative and no guard against that is needed.
This is the same ordering point as the visibility sweep above, pointing the other way. There, the comparison had to happen first so the running value meant strictly before. Here it has to happen second so the value means at or before. Decide which sentence you want and the order follows from it.
Two acceptable answers
The array version and the pointer version are both O(n) time. One is O(n) space and easy to justify; the other is O(1) space and needs the settled-side argument. Knowing both, and being able to say why the second one is correct, is a stronger position than only knowing the second.
Write the array version first, get it passing, then collapse it. Attempting the pointer version cold is how people end up with a loop that is nearly right and no way to tell which half is wrong.
Both sweeps, and something that needs them both
tallest_to_left returns a list where position i holds the tallest value strictly to the left of i, or 0 if there is nothing there. tallest_to_right does the mirror. visible_from_either_end uses both: a post is visible if it is taller than everything on at least one of its two sides.
Tests
print(tallest_to_left([3, 1, 4, 2])) print(tallest_to_right([3, 1, 4, 2])) print(visible_from_either_end([3, 1, 4, 2])) print(visible_from_either_end([1, 2, 3]), visible_from_either_end([]), visible_from_either_end([5]))
Output
Run the tests when you are ready.
Trapping Rain Water
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.