My tank finder says 40, but two walls hold 49

DSA · Core
25 min read, about 1 h 30 min with practice

Concept
Asked often: high
Reviewed 2026-11

New to some of the words above? Open a quick recap. Each takes about two minutes.

Quick recapBig-O in two minutes· 2 min

Big-O says how the work grows as the input grows. One loop over n items is O(n): twice the items, twice the work. A loop inside a loop is O(n²): twice the items, four times the work. Space is the same idea for the extra memory: a few numbers is O(1), a copy of the input is O(n). The full lesson: My code passed every test, then timed out on the big one.

Quick recapLists and indexes in two minutes· 2 min

A list keeps its items in a row, from index 0 to len(a) - 1, so a[i] is one step. a[-1] is the last item. A slice like a[2:5] is a copy of those items: O(k) for k items. Two indexes can walk a list from both ends: lo, hi = 0, len(a) - 1, then lo += 1 and hi -= 1 until they meet. The full lesson: I reversed the list, but the caller’s list didn’t change.

See the problem

The interview task: walls stand in a row, 1 apart. Pick two. Water fills the space between them, up to the shorter wall. Which two hold the most? You pick the two tallest:

def most_water(heights):
    tallest = sorted(range(len(heights)), key=lambda i: heights[i])[-2:]
    i, j = sorted(tallest)  # the two tallest walls, left one first
    return min(heights[i], heights[j]) * (j - i)

For the walls [1, 8, 6, 2, 5, 4, 8, 3, 7], it picks the two walls 8 tall, at 1 and 6. They are 5 apart, so they hold 8 × 5 = 40. But the 8 at 1 and the 7 at 8 are 7 apart, and hold 7 × 7 = 49.

The water depends on two things: the shorter wall, and how far apart they are. The two tallest can be close together. The two at the ends are the furthest apart, but they can be short.

Define the task

Write most_water(heights).

Input: heights, up to 200,000 walls, each 0 or more tall, 1 apart.
Output: the most water two walls hold. Walls i and j, with i < j, hold min(heights[i], heights[j]) × (j − i). The walls between them don’t get in the way. With fewer than 2 walls, it’s 0.
The hard part: 200,000 walls make 20 billion pairs. It must be fast anyway.

Example: most_water([1, 8, 6, 2, 5, 4, 8, 3, 7]) is 49, from walls 1 and 8.

Pause and think

Hints open one at a time:

Hint 1 of 3

The water can’t rise above the shorter wall. Pair the shorter end wall with any wall further in, and the tank is narrower, and still no taller.

Hint 2 of 3

So no tank with the shorter end wall beats this one. Rule it out, and move that end in by one.

Hint 3 of 3

Keep going: work out the water, keep the best, and move the shorter wall in. Stop when the two ends meet. That’s n − 1 tanks, not n²/2.

Understand the idea

Two pointers: one at each end, walking in. Keep lo at the left end and hi at the right. Each step looks at the pair lo and hi, then moves one of them in. They meet after n − 1 steps.

Each step rules out a whole wall. Say wall lo is the shorter. It caps the water at heights[lo]. Pair it with any wall further in, and the tank is narrower, with water no higher. So no tank with wall lo beats this one, and lo moves in, never to come back. One check stands in for every pair wall lo had left.

Moving the taller wall can’t help. The shorter wall still caps the water, and the tank gets narrower. So move the shorter one. On a tie, move either: neither can beat this tank with a wall further in.

Two pointers fit when one check can rule out an end. In a sorted list, a pair whose sum is too small needs a bigger number, so the left end moves right. That’s pair sum on a sorted list, in the Two Sum practice. Reversing a list in place walks in from both ends too. Another kind walks both pointers the same way: a slow one writes and a fast one reads, as when the arrays lesson moves the zeros. The next lesson, sliding window, is that kind.

Watch it. The faded walls are ruled out. Try your own walls, like 5, 5, 5, 5 for a tie, or 1, 2, 3, 4, 5 for walls that rise.

Two walls walking in

Work so far

tank now: shorter × width	none yet
best so far	0
tanks checked	0

Step 1 of 18. Start with the widest tank: the walls at both ends, lo = 0 and hi = 8. The water rises to the shorter wall.

Speed Ask me first Show as text

1def most_water(heights: list[int]) -> int:
2    lo, hi = 0, len(heights) - 1  # the widest tank
3    best = 0
4    while lo < hi:
5        water = min(heights[lo], heights[hi]) * (hi - lo)
6        best = max(best, water)
7        if heights[lo] < heights[hi]:
8            lo += 1  # no tank with the shorter wall further in holds more
9        else:
10            hi -= 1
11    return best

Climb the ladder

All three give 49 for the example. What changes is how many tanks they check.

The idea: For every pair of walls, i before j, work out the water and keep the best.

It’s the rule, word for word, so it’s easy to trust.

def most_water(heights: list[int]) -> int:
    best = 0
    for i in range(len(heights)):
        for j in range(i + 1, len(heights)):
            water = min(heights[i], heights[j]) * (j - i)
            best = max(best, water)
    return best

Time: O(n²)
Space: O(1)
Why: n walls make n(n − 1)/2 pairs, and it works out the water for each one.

Where it breaks: 200,000 walls make about 20 billion pairs. It runs out of time on the first speed test.

The idea: For each wall i, try the furthest wall first. The water is at most heights[i] tall, so once heights[i] × (j − i) can’t beat the best, stop: every closer wall j makes a narrower tank still.

The waste in Okay: it works out tanks that can’t win. A tank is at most as tall as its left wall, so most of them can be skipped.

Highlighted lines are new in this rung.

def most_water(heights: list[int]) -> int:
    best = 0
    n = len(heights)
    for i in range(n):
        for j in range(n - 1, i, -1):  # the widest first
            if heights[i] * (j - i) <= best:
                break  # the water is at most heights[i] tall, so no narrower tank can win
            water = min(heights[i], heights[j]) * (j - i)
            best = max(best, water)
    return best

Time: O(n²) at worstwas O(n²)
Space: O(1)
Why: When the walls rise to the right, the cut stops almost at once: under 2n checks. When they get lower, wall i is the taller of each pair, so heights[i] says little, and it checks about n²/5 pairs.

What changed from the previous rung

def most_water(heights: list[int]) -> int:
    best = 0
    for i in range(len(heights)):
        for j in range(i + 1, len(heights)):
    n = len(heights)
    for i in range(n):
        for j in range(n - 1, i, -1):  # the widest first
            if heights[i] * (j - i) <= best:
                break  # the water is at most heights[i] tall, so no narrower tank can win
            water = min(heights[i], heights[j]) * (j - i)
            best = max(best, water)
    return best

Where it breaks: walls that get lower to the right. 200,000 of them take about 8 billion checks. It runs out of time on the second speed test, though the rising walls are quick.

The idea: Start lo and hi at the two ends. Work out their tank and keep the best. Then move the shorter one in: no tank with it beats this one. Stop when they meet.

The waste in Better: its cut only knows the left wall. Two pointers rule out the shorter of the two, so every step counts.

Highlighted lines are new in this rung.

def most_water(heights: list[int]) -> int:
    lo, hi = 0, len(heights) - 1  # the widest tank
    best = 0
    while lo < hi:
        water = min(heights[lo], heights[hi]) * (hi - lo)
        best = max(best, water)
        if heights[lo] < heights[hi]:
            lo += 1  # no tank with the shorter wall further in holds more
        else:
            hi -= 1
    return best

Time: O(n)was O(n²) at worst
Space: O(1)
Why: Each step rules out one wall, so n walls take n − 1 steps, whatever their heights.

What changed from the previous rung

def most_water(heights: list[int]) -> int:
    lo, hi = 0, len(heights) - 1  # the widest tank
    best = 0
    n = len(heights)
    for i in range(n):
        for j in range(n - 1, i, -1):  # the widest first
            if heights[i] * (j - i) <= best:
                break  # the water is at most heights[i] tall, so no narrower tank can win
            water = min(heights[i], heights[j]) * (j - i)
            best = max(best, water)
    while lo < hi:
        water = min(heights[lo], heights[hi]) * (hi - lo)
        best = max(best, water)
        if heights[lo] < heights[hi]:
            lo += 1  # no tank with the shorter wall further in holds more
        else:
            hi -= 1
    return best

When Best isn’t best: when the walls between do matter. For the water left on top of every bar after rain, each bar needs the tallest on both sides. Two pointers still work there, with a different rule: that’s the third practice problem.

Write it yourself

Now write it in the page. Press Run tests to check your code. Python runs in your browser, so nothing is sent anywhere. Your code is saved in this browser for next time.

Try Okay from the ladder first: it runs out of time on the walls that rise. Better passes that one, but runs out of time on the walls that get lower.

Hold the most water

Ctrl + Enter runs

Loads about 6 MB the first time. Best on Wi-Fi.

Not run yet: most_water([1, 8, 6, 2, 5, 4, 8, 3, 7]) → 49
Not run yet: most_water([1, 1]) → 1
Not run yet: most_water([2, 9, 9, 1, 1, 1, 1, 1, 1, 2]): the two tallest walls hold just 9 → 18
Not run yet: most_water([4, 3, 2, 1, 4]) → 16
Not run yet: most_water([5, 5, 5, 5]): walls of the same height → 15
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Speed test: 200,000 walls, each taller than the last → 10000000000
Not run yet: Speed test: 200,000 walls, each lower than the last → 10000000000

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Compare

Way	Time	Extra memory	Good	Not so good	Use it when
Okay: every pair	O(n²)	O(1)	It’s the rule, word for word	Works out every tank, even ones that can’t win	A few walls, checked by hand
Better: every pair, with a cut	O(n²) at worst	O(1)	Skips most tanks when the walls rise	Walls that get lower defeat the cut	Hardly ever: Best is as short
Best: two pointers	O(n)	O(1)	n − 1 tanks, whatever the heights	Needs the reason to trust it	Always, for this problem

How much work is that? Each bar is one rung, for n walls that get lower to the right, where Better’s cut helps least. Pick a size, or run the race.

Checking n walls that get lower

OkayCheck every pair · O(n²)≈ 20,000,000,000 tanks checked
BetterEvery pair, with a cut · O(n²) at worst≈ 8,000,000,000 tanks checked
BestTwo pointers · O(n)≈ 200,000 tanks checked

At n = 200,000, Okay does about 100,000 times more work than Best.

Every bar does the same number of steps per second, so the race shows which rung finishes first. Turn on Log scale to compare the short bars.

Better checks about two fifths as many tanks as Okay, but both grow as n². Best checks one tank for each wall it rules out: n − 1.

Every step here is a step of Python, so the race is close to the real times. In this page’s Python, 10,000 walls take Okay about 5 to 15 seconds, depending on the computer. Better, on walls that get lower, takes half to two thirds as long. Twice as many walls take each about 4 times as long. Best takes a tenth of a second or less for 200,000 walls.

Common mistakes and edge cases

The width is j − i. Walls 1 and 8 are 7 apart. Count the gaps, not the walls.
Stop at lo < hi. When they meet, it’s one wall, and one wall holds no water. In pair problems, lo <= hi would pair an item with itself.
Fewer than 2 walls. For an empty list, hi starts at -1, so the loop never runs and it returns 0. Test it anyway.
Two pointers need a reason to move. Here, it’s the shorter wall. In a sorted list, it’s the sum. With no reason, like pair sum on a list that isn’t sorted, sort first, or use a hash map.

Say it in the interview

Questions to ask first

Are the walls all 1 apart? Can a wall be 0 tall?
Do the walls between get in the way? Here they don’t.
Do you want the amount of water, or the two walls?

A 60-second walkthrough

“I’ll start with the two walls at the ends, the widest tank, and keep the best water so far: the shorter height times the distance. Then I move the shorter wall in. That’s safe: any tank with the shorter wall and a wall further in is narrower and no taller, so it can’t beat the one I just checked. On a tie, either can go. The pointers meet after n minus 1 steps, so it’s O(n) time and O(1) memory, against O(n²) for every pair.”

Likely follow-ups

Which two walls? Keep lo and hi when the best changes.
Why not the two tallest? They can be close together: 40, when 49 fits.
Why is it safe? A wall is ruled out only when every tank it could still make is narrower and no taller than one just checked. So the best tank is checked, or one just as big.
The water left on every bar after rain? That’s trapping rain water, the third practice problem. Two pointers work there too.

Practice

Three problems, from easy to hard: a palindrome with one letter deleted, packing items two to a box, and rain on a row of bars. Each has hints, tests you can run here, and its own Okay, Better and Best answers. For each rung, say its Big-O before you open it.

1. A palindrome, if you delete one letter (easy)

Write almost_palindrome(s). Return True if s reads the same both ways, or would after deleting one letter. s is lower-case letters only.

Example: almost_palindrome("abca") is True: delete the b, or the c. almost_palindrome("abc") is False.

Hint 1 of 3

Walk in from both ends while the letters match. The first time they don’t, one of those two letters has to go.

Hint 2 of 3

You don’t know which, so try both: skip the left letter, or the right one. Either way, what’s left between has to read the same both ways.

Hint 3 of 3

Check what’s left with two more pointers, from where you are. Nothing needs to be copied.

A palindrome, if you delete one letter

Ctrl + Enter runs

Loads about 6 MB the first time. Best on Wi-Fi.

Not run yet: almost_palindrome('aba') → True
Not run yet: almost_palindrome('abca') → True
Not run yet: almost_palindrome('abc') → False
Not run yet: almost_palindrome("deeee"): the letter to delete is the first → True
Not run yet: almost_palindrome("ebcbbececabbacecbbcbe"): both skips start well, and only the left one works → True
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Speed test: a million letters, and only deleting the last one works → True

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Show the Okay, Better and Best answers

The idea: If s reads the same both ways, that’s it. If not, delete each letter in turn, and check what’s left against its reverse.

It tries every way there is, so it can’t miss one.

def almost_palindrome(s: str) -> bool:
    if s == s[::-1]:
        return True
    for k in range(len(s)):
        t = s[:k] + s[k + 1 :]  # s without letter k
        if t == t[::-1]:
            return True
    return False

Time: O(n²)
Space: O(n)
Why: n tries, and each builds and reverses a string of n − 1 letters.

Where it breaks: a million letters, where only deleting the last one works. That’s a million tries of a million letters each. It runs out of time.

The idea: Walk in from both ends to the first letters that don’t match. Slice out what’s left without the left one, and without the right one, and check whether either reads the same both ways.

The waste in Okay: it tries deletions that can’t help. Only the two letters at the first mismatch can be the one to go.

Highlighted lines are new in this rung.

def almost_palindrome(s: str) -> bool:
    lo, hi = 0, len(s) - 1
    while lo < hi:
        if s[lo] != s[hi]:
            no_left = s[lo + 1 : hi + 1]  # delete the left letter
            no_right = s[lo:hi]  # or the right one
            return no_left == no_left[::-1] or no_right == no_right[::-1]
        lo += 1
        hi -= 1
    return True

Time: O(n)was O(n²)
Space: O(n)
Why: One walk in, then two slices of up to n letters, each checked once.

What changed from the previous rung

def almost_palindrome(s: str) -> bool:
    if s == s[::-1]:
        return True
    for k in range(len(s)):
        t = s[:k] + s[k + 1 :]  # s without letter k
        if t == t[::-1]:
            return True
    return False
    lo, hi = 0, len(s) - 1
    while lo < hi:
        if s[lo] != s[hi]:
            no_left = s[lo + 1 : hi + 1]  # delete the left letter
            no_right = s[lo:hi]  # or the right one
            return no_left == no_left[::-1] or no_right == no_right[::-1]
        lo += 1
        hi -= 1
    return True

Where it breaks: it passes every test here. But each slice is a copy: for a million letters, two new strings of up to a million each.

The idea: The same, but check what’s left with two more pointers, from the mismatch in. Nothing is copied.

The waste in Better: the slices copy letters only to read them once. Pointers read them where they are.

Highlighted lines are new in this rung.

def almost_palindrome(s: str) -> bool:
    def mirrored(lo: int, hi: int) -> bool:
        while lo < hi:
            if s[lo] != s[hi]:
                return False
            lo += 1
            hi -= 1
        return True

    lo, hi = 0, len(s) - 1
    while lo < hi:
        if s[lo] != s[hi]:
            return mirrored(lo + 1, hi) or mirrored(lo, hi - 1)  # delete one or the other
        lo += 1
        hi -= 1
    return True

Time: O(n)
Space: O(1)was O(n)
Why: Each letter is read at most about twice, and it keeps just a few numbers.

What changed from the previous rung

def almost_palindrome(s: str) -> bool:
    def mirrored(lo: int, hi: int) -> bool:
        while lo < hi:
            if s[lo] != s[hi]:
                return False
            lo += 1
            hi -= 1
        return True

    lo, hi = 0, len(s) - 1
    while lo < hi:
        if s[lo] != s[hi]:
            no_left = s[lo + 1 : hi + 1]  # delete the left letter
            no_right = s[lo:hi]  # or the right one
            return no_left == no_left[::-1] or no_right == no_right[::-1]
            return mirrored(lo + 1, hi) or mirrored(lo, hi - 1)  # delete one or the other
        lo += 1
        hi -= 1
    return True

When Best isn’t best: more deletions. With up to k, the two tries split again at every mismatch: up to 2ᵏ ways. For a big k, find the longest palindrome you can keep, with dynamic programming, instead.

2. The fewest boxes, two items each (medium)

Write fewest_boxes(weights, limit). A box holds one item or two, and at most limit in all. No item weighs more than limit. Return the fewest boxes that hold every item. Don’t change the list you’re given.

Example: fewest_boxes([3, 2, 2, 1], 3) is 3: 1 and 2 share a box, and 2 and 3 go alone.

Hint 1 of 3

Sort the weights. The heaviest item needs a box. Which item, if any, should go beside it?

Hint 2 of 3

If even the lightest doesn’t fit beside the heaviest, nothing does: the heaviest goes alone. If the lightest fits, put it in. It costs nothing: the lightest fits beside anything the heaviest could.

Hint 3 of 3

Keep lo at the lightest and hi at the heaviest. Each box takes hi, and lo too if it fits. Stop when they cross.

The fewest boxes, two items each

Ctrl + Enter runs

Loads about 6 MB the first time. Best on Wi-Fi.

Not run yet: fewest_boxes([1, 2], 3) → 1
Not run yet: fewest_boxes([3, 2, 2, 1], 3) → 3
Not run yet: fewest_boxes([3, 5, 3, 4], 5) → 4
Not run yet: fewest_boxes([1, 1, 1], 9): two to a box at most → 2
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Speed test: 60,000 items of 9 and one of 1, with a limit of 10 → 60000
Not run yet: Speed test: 500,000 items of 1 and 500,000 of 9, with a limit of 10 → 500000

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Show the Okay, Better and Best answers

The idea: Sort a copy. Take the heaviest item. Look down the rest, from the heaviest, for one that fits beside it, and take that too. Repeat until none are left.

It packs each box as full as it can, which is a safe way to get the fewest.

def fewest_boxes(weights: list[int], limit: int) -> int:
    items = sorted(weights)
    boxes = 0
    while items:
        heavy = items.pop()  # the heaviest goes in a box
        for k in range(len(items) - 1, -1, -1):  # look for the heaviest that fits beside it
            if heavy + items[k] <= limit:
                items.pop(k)
                break
        boxes += 1
    return boxes

Time: O(n²)
Space: O(n)
Why: Each box can look past every item left: up to n looks for each of up to n boxes.

Where it breaks: 60,000 items of 9 and one of 1. Only the 1 fits beside a 9, so after the first box, each 9 looks past every 9 left and finds none: about 1.8 billion looks. It runs out of time.

The idea: Sort a copy. Take the heaviest with pop(). Find the heaviest that fits beside it with bisect, and take it out with pop(k).

The waste in Okay: it reads the items one by one to find a partner. They’re sorted, so binary search finds it in a few steps.

Highlighted lines are new in this rung.

from bisect import bisect_right


def fewest_boxes(weights: list[int], limit: int) -> int:
    items = sorted(weights)
    boxes = 0
    while items:
        heavy = items.pop()  # the heaviest goes in a box
        k = bisect_right(items, limit - heavy) - 1  # the heaviest that fits beside it
        if k >= 0:
            items.pop(k)  # moves every item after k
        boxes += 1
    return boxes

Time: O(n²)
Space: O(n)
Why: bisect finds the item in O(log n), but pop(k) moves every item after k one place left: up to n each time.

What changed from the previous rung

from bisect import bisect_right


def fewest_boxes(weights: list[int], limit: int) -> int:
    items = sorted(weights)
    boxes = 0
    while items:
        heavy = items.pop()  # the heaviest goes in a box
        for k in range(len(items) - 1, -1, -1):  # look for the heaviest that fits beside it
            if heavy + items[k] <= limit:
                items.pop(k)
                break
        k = bisect_right(items, limit - heavy) - 1  # the heaviest that fits beside it
        if k >= 0:
            items.pop(k)  # moves every item after k
        boxes += 1
    return boxes

Where it breaks: 500,000 of each. Each 1 taken out moves every 9 after it: about 125 billion moves. It runs out of time on the second speed test. The first is quick: with one 1, there’s just one pop(k).

The idea: Sort a copy. Keep lo at the lightest and hi at the heaviest. Each box takes hi, and lo too if it fits. Stop when they cross.

The waste in Better: it takes items out of the middle of a list, which moves the rest. Two pointers just step past them.

Highlighted lines are new in this rung.

def fewest_boxes(weights: list[int], limit: int) -> int:
    items = sorted(weights)
    lo, hi = 0, len(items) - 1
    boxes = 0
    while lo <= hi:
        if items[lo] + items[hi] <= limit:
            lo += 1  # the lightest fits beside the heaviest
        hi -= 1  # the heaviest goes in a box either way
        boxes += 1
    return boxes

Time: O(n log n)was O(n²)
Space: O(n)
Why: The sort is O(n log n). Then each box moves hi, and maybe lo: O(n). Nothing is taken out of the list.

What changed from the previous rung

from bisect import bisect_right


def fewest_boxes(weights: list[int], limit: int) -> int:
    items = sorted(weights)
    lo, hi = 0, len(items) - 1
    boxes = 0
    while items:
        heavy = items.pop()  # the heaviest goes in a box
        k = bisect_right(items, limit - heavy) - 1  # the heaviest that fits beside it
        if k >= 0:
            items.pop(k)  # moves every item after k
    while lo <= hi:
        if items[lo] + items[hi] <= limit:
            lo += 1  # the lightest fits beside the heaviest
        hi -= 1  # the heaviest goes in a box either way
        boxes += 1
    return boxes

When Best isn’t best: three or more to a box. Then it’s bin packing, and no quick rule always finds the fewest. Putting each item, from the heaviest, in the first box it fits is a good guess.

3. Rain on a row of bars (hard)

Write trapped_water(heights). Bars of these heights stand side by side, each 1 wide. After rain, how much water stays on top of them? Over each bar, the water rises to the lower of two: the tallest bar up to it from the left, and the tallest from the right. Each count includes the bar itself.

Example: trapped_water([4, 2, 0, 3, 2, 5]) is 9. The water rises to 4 between the first and last bars: 2 over the first 2, 4 over the 0, 1 over the 3 and 2 over the second 2.

Hint 1 of 3

Over each bar, the water rises to the lower of the tallest on its left and the tallest on its right. Take away the bar itself.

Hint 2 of 3

Work out the tallest so far from the left, for every bar, in one pass. Do the same from the right. Then add it up.

Hint 3 of 3

With two pointers: keep the tallest seen from each end. Move in from the side whose bar is lower. The other side has a bar at least as tall, so the water there is set by its own side’s tallest.

Rain on a row of bars

Ctrl + Enter runs

Loads about 6 MB the first time. Best on Wi-Fi.

Not run yet: trapped_water([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) → 6
Not run yet: trapped_water([4, 2, 0, 3, 2, 5]) → 9
Not run yet: trapped_water([1, 2, 3, 4]): the water runs off the low end → 0
Not run yet: trapped_water([2, 0, 2, 0, 2]) → 4
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Speed test: 200,002 bars, from 0 to 999 tall → 99900000

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Show the Okay, Better and Best answers

The idea: For each bar, find the tallest bar on its left and on its right, with max() over a slice. The water over it is the lower of the two, minus the bar.

It does what the rule says, one bar at a time.

def trapped_water(heights: list[int]) -> int:
    total = 0
    for i in range(len(heights)):
        left = max(heights[: i + 1])  # the tallest bar up to i
        right = max(heights[i:])  # the tallest bar from i on
        total += min(left, right) - heights[i]
    return total

Time: O(n²)
Space: O(n)
Why: Each bar reads every other bar, in two slices.

Where it breaks: 200,000 bars. Each one reads all the others: about 40 billion reads. It runs out of time.

The idea: In one pass from the left, keep the tallest so far for each bar in a list. In one pass from the right, the same. Then add min(left[i], right[i]) − heights[i] for each bar.

The waste in Okay: it finds the same tallest bars again for every bar. The tallest up to i is the tallest up to i − 1, or bar i.

Highlighted lines are new in this rung.

def trapped_water(heights: list[int]) -> int:
    n = len(heights)
    left = [0] * n  # left[i]: the tallest bar up to i
    right = [0] * n  # right[i]: the tallest bar from i on
    for i in range(n):
        left[i] = max(heights[i], left[i - 1] if i > 0 else 0)
    for i in range(n - 1, -1, -1):
        right[i] = max(heights[i], right[i + 1] if i < n - 1 else 0)
    return sum(min(left[i], right[i]) - heights[i] for i in range(n))

Time: O(n)was O(n²)
Space: O(n)
Why: Three passes of n, and two lists of n.

What changed from the previous rung

def trapped_water(heights: list[int]) -> int:
    total = 0
    for i in range(len(heights)):
        left = max(heights[: i + 1])  # the tallest bar up to i
        right = max(heights[i:])  # the tallest bar from i on
        total += min(left, right) - heights[i]
    return total
    n = len(heights)
    left = [0] * n  # left[i]: the tallest bar up to i
    right = [0] * n  # right[i]: the tallest bar from i on
    for i in range(n):
        left[i] = max(heights[i], left[i - 1] if i > 0 else 0)
    for i in range(n - 1, -1, -1):
        right[i] = max(heights[i], right[i + 1] if i < n - 1 else 0)
    return sum(min(left[i], right[i]) - heights[i] for i in range(n))

Where it breaks: it passes every test here. But it keeps two lists as long as the input.

The idea: Keep lo and hi at the ends, and the tallest seen from each side. Move in from the lower side, and add its tallest minus the bar: the far side has a bar at least as tall, so the water can’t run off that way.

The waste in Better: it keeps the tallest so far from both sides for every bar. Each bar only needs the lower side’s, and two pointers always work on the lower side.

Highlighted lines are new in this rung.

def trapped_water(heights: list[int]) -> int:
    lo, hi = 0, len(heights) - 1
    left_max = right_max = 0  # the tallest bar seen from each end
    total = 0
    while lo < hi:
        if heights[lo] < heights[hi]:
            left_max = max(left_max, heights[lo])
            total += left_max - heights[lo]  # a taller bar on the right holds it in
            lo += 1
        else:
            right_max = max(right_max, heights[hi])
            total += right_max - heights[hi]
            hi -= 1
    return total

Time: O(n)
Space: O(1)was O(n)
Why: One pass, and four numbers.

What changed from the previous rung

def trapped_water(heights: list[int]) -> int:
    n = len(heights)
    left = [0] * n  # left[i]: the tallest bar up to i
    right = [0] * n  # right[i]: the tallest bar from i on
    for i in range(n):
        left[i] = max(heights[i], left[i - 1] if i > 0 else 0)
    for i in range(n - 1, -1, -1):
        right[i] = max(heights[i], right[i + 1] if i < n - 1 else 0)
    return sum(min(left[i], right[i]) - heights[i] for i in range(n))
    lo, hi = 0, len(heights) - 1
    left_max = right_max = 0  # the tallest bar seen from each end
    total = 0
    while lo < hi:
        if heights[lo] < heights[hi]:
            left_max = max(left_max, heights[lo])
            total += left_max - heights[lo]  # a taller bar on the right holds it in
            lo += 1
        else:
            right_max = max(right_max, heights[hi])
            total += right_max - heights[hi]
            hi -= 1
    return total

When Best isn’t best: rain on a map of heights, not a row. Water can run off in any direction, so it takes a heap, working in from the lowest edge.

Check yourself

A few quick questions. Ones you miss are remembered, so you can find your weak spots later.

Predict the outputWhat does this print?

h = [3, 1, 2, 4]
lo, hi = 0, len(h) - 1
while lo < hi:
    if h[lo] < h[hi]:
        lo += 1
    else:
        hi -= 1
print(lo)

0123

Multiple choiceWalls 2 and 7 are 4 and 9 tall. How much water do they hold?
20243645

Spot the bugThis should return the most water two walls hold. What's wrong?

def most_water(heights):
    lo, hi = 0, len(heights) - 1
    best = 0
    while lo < hi:
        best = max(best, min(heights[lo], heights[hi]) * (hi - lo))
        if heights[lo] > heights[hi]:
            lo += 1
        else:
            hi -= 1
    return best

It moves the taller wall in, so it can skip the best tankThe width should be hi − lo + 1The loop should run while lo <= hiNothing

Multiple choiceIn the most water problem, why is it safe to rule out the shorter of walls lo and hi?
Every tank it makes with a wall further in is narrower and no tallerThe shorter wall is never in the best tankThe taller wall is always in the best tankIt isn’t, but it works on most inputs
Pick the patternYou have a sorted list of prices. Do two of them add up to exactly the value of a gift card? Use O(1) extra memory.
Two pointers, from both endsA set of the prices seen so farCheck every pairA dict from each price to how many times it comes

Flashcards

Add these to your review deck. Each card comes back a little later every time you get it right.

Cheat sheet

Two pointers: lo, hi = 0, len(a) - 1, then move one in each step until lo < hi fails. n items take about n steps.
Each step must rule out an end, so it never comes back. Say why before you code it.
Most water: move the shorter wall. It caps the water, and every tank it could still make is narrower.
Pair sum on a sorted list: too small, lo += 1; too big, hi -= 1.
Same direction: a slow pointer writes and a fast one reads, to change a list in place.
while lo < hi, so an item never pairs with itself.
Two pointers need O(1) extra memory: no slices, no copies.

Go deeper

Step through more: Most water on the DSA visualizer, and two pointers on a sorted list.
Two Sum finds a pair on a sorted list with two pointers, and its practice has Three Sum.
The arrays lesson moves the zeros with a slow and a fast pointer.
Next on the DSA roadmap: sliding window.

Can you do these now?

If you’re not sure of any of these, scroll back to that part before moving on.

Walk two pointers in from both ends, and say why each step rules an item out
Find the most water two walls can hold in O(n)
Tell when two pointers fit, and which pointer to move
Use two pointers to check a palindrome, pack pairs, and trap rain water

Status: Not started

My tank finder says 40, but two walls hold 49

See the problem

Define the task

Pause and think

Understand the idea

Climb the ladder

Check every pair

Every pair, with a cut

Two pointers from the ends

Write it yourself

Hold the most water

Compare

Common mistakes and edge cases

Say it in the interview

Practice

1. A palindrome, if you delete one letter (easy)

A palindrome, if you delete one letter

Try every deletion

Two pointers, then two slices

Two pointers all the way

2. The fewest boxes, two items each (medium)

The fewest boxes, two items each

The heaviest, with the heaviest that fits

The same, with binary search

Two pointers: the lightest beside the heaviest

3. Rain on a row of bars (hard)

Rain on a row of bars

For each bar, look both ways

Two passes of the tallest so far

Two pointers from the ends

Check yourself

Flashcards

Cheat sheet

Go deeper

Can you do these now?