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.

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.

1def visible_from_left(heights):2    """Posts taller than everything before them, so nothing blocks the view."""3    seen = []4    running = 05    for i, height in enumerate(heights):6        if height > running:            # compare before absorbing7            seen.append(i)8        running = max(running, height)9    return seen10 11print(visible_from_left([3, 1, 4, 2, 5]))

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.

1heights = [2, 6, 1, 1, 3, 5]2left, right = 0, len(heights) - 13tallest_left = tallest_right = 04 5for _ in range(3):6    tallest_left = max(tallest_left, heights[left])7    tallest_right = max(tallest_right, heights[right])8    settled = "left" if tallest_left < tallest_right else "right"9    print(f"tallest_left={tallest_left}, tallest_right={tallest_right} -> {settled} is settled")10    if settled == "left":11        left += 112    else:13        right -= 1

Neither running maximum can ever shrink, which is what makes the smaller one safe to act on.

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.

Code lab· 20 min

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.

solution.py

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 tests to see output.

Problem· 35 min

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.

A per-position quantity

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.

1def visible_from_left(heights):2 """Posts taller than everything before them, so nothing blocks the view."""3 seen = []4 running = 05 for i, height in enumerate(heights):6 if height > running: # compare before absorbing7 seen.append(i)8 running = max(running, height)9 return seen10 11print(visible_from_left([3, 1, 4, 2, 5]))

1heights = [2, 6, 1, 1, 3, 5]2left, right = 0, len(heights) - 13tallest_left = tallest_right = 04 5for _ in range(3):6 tallest_left = max(tallest_left, heights[left])7 tallest_right = max(tallest_right, heights[right])8 settled = "left" if tallest_left < tallest_right else "right"9 print(f"tallest_left={tallest_left}, tallest_right={tallest_right} -> {settled} is settled")10 if settled == "left":11 left += 112 else:13 right -= 1

Two acceptable answers

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.

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]))