DSA sheet · Arrays · Two Pointers pattern

Trapping Rain Water

The teacher closes the two-pointer array problems with this famous hard question. Bars of different heights stand side by side; after rain, how much water stays trapped between them? She builds the answer one index at a time: the water above any bar depends on the tallest bar to its left and the tallest bar to its right. The brute force finds those two maxima with fresh loops for every index (O(n²)). Then, borrowing the idea from Container With Most Water, she uses two pointers from both ends with a running left_max and right_max, and finishes in one O(n) pass.

Why it matters: the key idea is that you don't always need to know both sides exactly; you only need to know which side is the limit. That one observation turns O(n²) into O(n) with O(1) space.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

Part 0 · What you must know before starting (two pointers from scratch)
Part A · Brute force: find left max and right max for every index
Part B · Optimal: two pointers with left_max and right_max
Part C · Revision page

Part 0 · Before starting

What is a pointer here?

A pointer is a variable that holds an index. left = 3 means "left points at index 3", and height[left] is the bar there.

The brute force, and why the array's shape lets us skip work

Many array questions look at pairs, or at "everything to the left and everything to the right" of each index. Doing that with fresh nested loops costs O(n²). Two pointers avoid it by walking inward from both ends and remembering what they've seen (here: the tallest bar so far on each side), so nothing is scanned twice.

Opposite-end pointers, and how they decide who moves

left starts at index 0, right at index n − 1, and every step moves one of them inward until they meet. The rule for which one moves must make sure that the side we move can be finished now without missing anything. In Container With Most Water, the rule was "move the shorter wall, because it can't do better". Here it will be "move the side whose maximum is smaller, because that side's water is already decided" (Part B, step 4).

kind	how the pointers move	example
Opposite ends (this page)	left from the start, right from the end, towards each other	Container With Most Water, this problem, palindromes
Same direction	slow/fast (write/read), both moving right	Move Zeroes
Three pointers	low, mid, high	Sort Colors
Fix one + two pointers	a loop fixes one value, opposite ends search the rest	3Sum

Left max and right max

For an index i, the left max is the tallest bar from index 0 up to i (including i). The right max is the tallest bar from i to the last index (including i). These two numbers are all we need to know how much water sits on top of bar i.

Why two pointers and not sliding window, prefix sum or Kadane's?

Sliding window, prefix sum and Kadane's are for a contiguous subarray where we combine all the values inside (a sum, an average, a length). Here, for each index we need just two special bars, the tallest on each side, not everything in between. "Two points, not everything between them" → two pointers.

Part A · Brute force: find left max and right max for every index

LeetCode 42

1The question in simple words

You get a list height of n non-negative numbers. Each number is a bar of that height, and every bar is 1 unit wide. Rain falls on top. Return how many units of water stay trapped between the bars.

  height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]     (██ = bar, ~~ = trapped water)

  3 |                      ██
  2 |          ██ ~~ ~~ ~~ ██ ██ ~~ ██
  1 |    ██ ~~ ██ ██ ~~ ██ ██ ██ ██ ██ ██
    +-------------------------------------
      0  1  2  3  4  5  6  7  8  9  10 11   index
      0  1  0  2  1  0  1  3  2  1  2  1   height
      0  0  1  0  1  2  1  0  0  1  0  0   water

Total water = 1 + 1 + 2 + 1 + 1 = 6.

The teacher starts by reading the first few bars: heights 0, 1, 0, 2. Between the bar of height 1 and the bar of height 2 there is one empty cell, and water fills it up to the lower of the two, height 1. Width 1 × height 1 = 1 unit.

Doubt: how is this different from Container With Most Water?
→ There, only two chosen lines mattered and the lines in between took no space. Here every bar is a solid block that takes up space, and water collects over every low spot, not just between two chosen walls. Where a block stands, water can't be; so blocks are subtracted.

2What the constraints tell us

1 ≤ n ≤ 2 × 10⁴. n² = 4 × 10⁸, which is past the roughly 10⁸ operations that run in time. So O(n²) is too slow (the teacher expects TLE); we need to optimise.
0 ≤ height[i] ≤ 10⁵. Heights can be 0: an empty spot with no bar, like index 0 and index 2 above. The total water is at most about 2 × 10⁴ × 10⁵ = 2 × 10⁹, which Python handles easily.

3Intuition: stand on one bar and look both ways

Don't think about whole "pools". Think about one index at a time: "how much water sits right on top of this bar?" Add those up and you have the answer.

Stand at index i and look left: you see the tallest bar on your left. Look right: you see the tallest bar on your right. Water above you rises until it would spill over the lower of those two walls. Then take away your own bar, because where your bar is, there's no room for water.

Water on one indexwater[i] = min(left_max, right_max) − height[i]
left_max / right_max = tallest bar on each side (including i itself)

4Building the logic from examples

No wall on one side → no water

Stand at index 0. There's nothing to its left, so nothing can hold water in. Water needs two walls with a dip between them. A single bar on its own can't hold anything. That's why the first and last index never hold water.

The teacher's short example: nearest wall or tallest wall?

  height = [3, 0, 2, 0, 4]

  4 |             ██
  3 | ██          ██
  2 | ██    ██    ██
  1 | ██    ██    ██
    +----------------
      0  1  2  3  4   index

Stand at index 1 (height 0). Do we use the nearest taller bar on the right (the 2 at index 2) or the tallest bar on the right (the 4 at index 4)? The teacher says: the tallest. The water over index 1 isn't stopped by the 2, because the water can rise above the 2 and is still held in by the 4 further away. So the level depends on the maximum on each side, not the nearest bar.

Index 1: left max = 3, right max = 4. Water rises to min(3, 4) = 3. Any higher and it spills over the 3 on the left. Bar here = 0 → water = 3 − 0 = 3.
Index 2: left max = 3, right max = 4 → level 3 again. But this time there's a bar of height 2 standing here, filling 2 of those 3 cells. So water = 3 − 2 = 1, not 3. This is why we subtract height[i].
Index 3: level 3, bar 0 → 3.

  4 |             ██
  3 | ██ ~~ ~~ ~~ ██
  2 | ██ ~~ ██ ~~ ██
  1 | ██ ~~ ██ ~~ ██
    +----------------
      0  1  2  3  4   index
      0  3  1  3  0   water  → total 7

Doubt 1: water = height × width, so why do we only use the height?
→ Every bar is exactly 1 wide, so the area over one index is (water height) × 1 = the water height.

Doubt 2: why include index i itself when finding the left max and the right max?
→ So the answer is never negative. If bar i is taller than everything around it, then left max = right max = height[i] (at least on the lower side), and the water is height[i] − height[i] = 0. That matches reality: a peak holds no water.

How to find left max and right max: two inner loops

For every index i, run one loop from i back to 0 to find the tallest bar on the left, and one loop from i to n − 1 to find the tallest on the right. Then add min(left_max, right_max) − height[i] to the total.

5Approach steps

water = 0.
For each index i:
left_max = tallest of height[0..i]; right_max = tallest of height[i..n−1].
water += min(left_max, right_max) − height[i].
Return water.

6Code (Python)

Brute force: O(n²), too slow for n = 2 × 10⁴

class Solution:
    def trap(self, height):
        n = len(height)
        water = 0
        for i in range(n):
            left_max = 0
            for j in range(0, i + 1):          # tallest bar from 0 to i
                left_max = max(left_max, height[j])
            right_max = 0
            for j in range(i, n):              # tallest bar from i to n-1
                right_max = max(right_max, height[j])
            water += min(left_max, right_max) - height[i]
        return water

7Code line by line

line	what it means
water = 0	Running total over all indexes.
for i in range(n):	Work out the water over each index, one by one.
left_max = 0 for j in range(0, i + 1): ...	Scan from the start up to i, keeping the tallest bar. Starting at 0 is safe because heights are never negative.
right_max = 0 for j in range(i, n): ...	Scan from i to the end, keeping the tallest bar.
min(left_max, right_max)	The water level over i: the lower of the two walls.
- height[i]	Take away the cells that bar i itself fills.

8Dry run (hand table)

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1].

i	height[i]	left_max (0..i)	right_max (i..11)	level = min	water here	total
0	0	0	3	0	0	0
1	1	1	3	1	0	0
2	0	1	3	1	1	1
3	2	2	3	2	0	1
4	1	2	3	2	1	2
5	0	2	3	2	2	4
6	1	2	3	2	1	5
7	3	3	3	3	0	5
8	2	3	2	2	0	5
9	1	3	2	2	1	6
10	2	3	2	2	0	6
11	1	3	1	1	0	6

9Complexity & remember

Time O(n²): for each of the n indexes, the two inner loops together scan all n bars again. With n = 2 × 10⁴ that's 4 × 10⁸ → too slow.
Space O(1).
The waste: the left max of index i and of index i + 1 are almost the same, yet we rescan from scratch each time. A running maximum fixes that.

Remember the brute forcePer index: min(tallest on left, tallest on right) − own height. Correct idea, but finding the two maxima by rescanning is O(n²).

Doubt (not in the video): could I store the left maxima and right maxima in two lists first?
→ Yes: one pass left-to-right builds all left maxima, one pass right-to-left builds all right maxima, then one pass adds up the water. That's O(n) time but O(n) extra space. The teacher skips straight to two pointers, which gets O(n) time with O(1) space.

Part B · Optimal: two pointers with left_max and right_max

LeetCode 42

1The question again, with the new goal

Same question, now in one O(n) pass with O(1) extra space, no rescanning.

2What the constraints tell us

n up to 2 × 10⁴ → O(n) is about 2 × 10⁴ steps: instant.
n ≥ 1 on LeetCode, so height[0] and height[n−1] exist. (Our code adds a one-line guard for an empty list anyway.)
Heights can be 0 → the end bars may be 0, which is fine: they just give a max of 0 to start with.

3Intuition: first try a running max from the left only

The teacher first asks: what if we walk from left to right, keep the tallest bar seen so far, and use only that?

Index 2 (height 0): tallest so far is 1 → water 1 − 0 = 1 ✓.
Index 3 (height 2): tallest so far becomes 2 → water 2 − 2 = 0 ✓.
Index 4 (height 1): tallest so far 2 → water 2 − 1 = 1 ✓.
Index 5 (height 0): tallest so far 2 → water 2 ✓.

It works on the left part because there's always a taller wall waiting on the right (the 3). But it fails near the right end: at index 9 (height 1) the tallest so far from the left is 3, so "left only" says water 3 − 1 = 2. The truth is 1, because on the right the tallest is only 2 and the water spills over it. So "left only" is safe only when we're sure the right side has a taller wall.

So, just like Container With Most Water, she starts from both ends: a running left_max for the left pointer, a running right_max for the right pointer, and a rule for which side to work on.

4Building the rule: why the side with the smaller max can be settled

Suppose at some moment left_max < right_max. Look at the next index on the left, left + 1. Its water is min(its true left max, its true right max) − its height.

Its true left max we know exactly: it's max(left_max, height[left+1]), because left has already walked over everything to its left.
Its true right max we don't know exactly, since we haven't seen the middle bars. But we know it is at least right_max, because the bar giving right_max lies to its right.
So the right wall is at least right_max, which is bigger than left_max. The minimum of the two walls is therefore decided by the left side. The middle bars can only make the right wall taller, never shorter, so they can't change the answer.

The rule in one sentenceIf left_max < right_max, the left side is the limit, so the water at the next left index is left_max − height, settled right now. Otherwise the right side is the limit, and we settle the next right index with right_max − height.

This is the same spirit as Container With Most Water: the smaller side is the one that decides the level, so it's the side we can finish and move past.

Doubt 1: what if the new bar is taller than left_max?
→ Then left_max first becomes that bar's height, and the water is left_max − height = 0. A new tallest bar has nothing taller on its left, so it can't hold water. That's why we update left_max before adding water: it can never go negative.

Doubt 2: why does the teacher first move the pointer, and only then add water?
→ The starting bars (index 0 and n − 1) are the outer edges, and a single edge bar can't hold water. So the loop first steps inward to a new index, updates the max, then adds that index's water. Each inner index is settled by whichever pointer reaches it first.

Doubt 3 (her bug on screen): can left_max and right_max start at 0?
→ No. She first started both at 0, and the submission failed. With 0 and 0, the first comparison 0 < 0 is false, so the right pointer moves, and the end bars were never included in the maxima. On [2, 0, 2] that gives 0 instead of 2. The fix she makes: start with left_max = height[0] and right_max = height[n−1], because the pointers begin standing on those bars.

Doubt 4: she compares left_max < right_max. I've seen height[left] < height[right] elsewhere. Which is right?
→ Both work. Comparing the maxima is the version that matches the reasoning above most directly, so the notes use hers. On a tie (equal maxima) either side can be settled; her code settles the right side.

Doubt 5: while left < right, not <=?
→ Yes, <. The pointers move inward until they stand on the same bar, and then there's nothing left between them. Going further would make them cross and count bars twice.

Doubt 6: in the last step one pointer steps onto the bar where the other one is standing. Is that bar counted twice?
→ It is visited twice, but the second visit always adds 0. A pointer only stays still while it stands on the tallest bar of its own side (otherwise it would still be the limit and keep moving). The pointer that moves has the smaller (or equal) max, so when it lands on that tallest bar, its max becomes that bar's height and the water is height − height = 0. In the dry run, index 7 is reached by right in step 7 and by left in step 11, both adding 0.

5Approach steps

left = 0, right = n − 1, left_max = height[0], right_max = height[n−1], water = 0.
While left < right:
If left_max < right_max: left += 1, left_max = max(left_max, height[left]), water += left_max − height[left].
Else: right −= 1, right_max = max(right_max, height[right]), water += right_max − height[right].
Return water.

6Code (Python)

Optimal: two pointers, O(n) time, O(1) space

class Solution:
    def trap(self, height):
        if not height:                         # guard (LeetCode always has n >= 1)
            return 0
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]   # NOT 0 (her fix)
        water = 0
        while left < right:
            if left_max < right_max:           # left side is the limit
                left += 1
                left_max = max(left_max, height[left])
                water += left_max - height[left]
            else:                              # right side is the limit
                right -= 1
                right_max = max(right_max, height[right])
                water += right_max - height[right]
        return water

7Code line by line

line	what it means
left, right = 0, len(height) - 1	Pointers on the two outer bars.
left_max, right_max = height[left], height[right]	Tallest bar seen so far on each side: at the start, just the bar each pointer stands on.
while left < right:	Keep going until the pointers meet; every inner bar gets settled once.
if left_max < right_max:	The left wall is the lower one, and the right side is guaranteed to have a wall at least right_max tall. So the left side decides the level.
left += 1	Step onto the next bar from the left.
left_max = max(left_max, height[left])	Include this bar in the left maximum (if it's a new tallest, its water will be 0).
water += left_max - height[left]	Level minus this bar's own height = water on this index.
else: right -= 1 ...	Mirror image: the right side is the limit, settle the next bar from the right with right_max.
return water	Water from the left side and the right side, added up.

8Dry run

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]. Start: left = 0, right = 11, left_max = 0, right_max = 1, water = 0. The "moved to" column is the index being settled in this step.

step	left	right	compare maxima	decision (which pointer moves, why)	bar at new spot	left_max / right_max after	water added	total
1	0→1	11	0 < 1	left is the limit → left +1	1	1 / 1	1 − 1 = 0	0
2	1	11→10	1 < 1? no	tie → else branch → right −1	2	1 / 2	2 − 2 = 0	0
3	1→2	10	1 < 2	left is the limit → left +1	0	1 / 2	1 − 0 = 1	1
4	2→3	10	1 < 2	left +1	2	2 / 2	2 − 2 = 0	1
5	3	10→9	2 < 2? no	tie → right −1	1	2 / 2	2 − 1 = 1	2
6	3	9→8	2 < 2? no	right −1	2	2 / 2	0	2
7	3	8→7	2 < 2? no	right −1	3	2 / 3	3 − 3 = 0	2
8	3→4	7	2 < 3	left is the limit → left +1	1	2 / 3	2 − 1 = 1	3
9	4→5	7	2 < 3	left +1	0	2 / 3	2 − 0 = 2	5
10	5→6	7	2 < 3	left +1	1	2 / 3	2 − 1 = 1	6
11	6→7	7	2 < 3	left +1 (lands on right's bar)	3	3 / 3	3 − 3 = 0	6
end	7	7	–	left = right → stop	–	–	–	6 ✓

Notice step 5: index 9 is settled from the right with right_max = 2, giving the correct 1. The "left only" idea would have said 2 there.

The bars at key moments. Yellow = where the pointers are, grey = already settled.

step 3010210132121left_max 1 < right_max 2 → index 2 gets 1

step 7010210132121right reaches the 3 → right_max 3; now the left side is the limit

step 11010210132121pointers meet on the tallest bar → done, total 6

L R

  final picture (same as the question):
  3 |                      ██
  2 |          ██ ~~ ~~ ~~ ██ ██ ~~ ██
  1 |    ██ ~~ ██ ██ ~~ ██ ██ ██ ██ ██ ██
    +-------------------------------------
      0  1  2  3  4  5  6  7  8  9  10 11
      -  L  L  L  L  L  L  R  R  R  R  -   settled by (- = edge bar)
                                           water 1+1+2+1+1 = 6

9Complexity & remember

Time O(n): every loop round moves one pointer one step inward, and each index is touched by only one of them, once. So the loop runs n − 1 times.
Space O(1): two pointers, two maxima, one total. No extra lists.

Remember Trapping Rain Water Water on a bar = min(left max, right max) − height.
Two pointers from the ends, maxima start at the end bars (not 0).
Smaller max = the limit: move that side in, update its max, add max − height.

Part C · Revision page

	Brute force (Part A)	Two pointers (Part B)
how left/right max is found	rescan both sides for every index	running max on each side as the pointers move in
water at an index	min(left max, right max) − height	(smaller side's max) − height
time / space	O(n²) / O(1)	O(n) / O(1)
n = 2 × 10⁴?	too slow	passes

	Container With Most Water	Trapping Rain Water
bars in between	thin, ignored	solid, subtracted
answer	one best container (max)	sum of water over every index
which pointer moves	the shorter wall	the side with the smaller max
why it's safe	the shorter wall can't do better	the smaller side already decides the level

If you remember only 5 lines 1. Think per index: water = min(tallest left, tallest right) − own height.
2. Use the tallest bar on each side, not the nearest one.
3. Brute force rescans for every index: O(n²).
4. Two pointers: if left_max < right_max, the left side is settled (the right wall is at least right_max); else the right side is.
5. Start the maxima at height[0] and height[n−1], move first, update max, then add.

Mistakes to avoid ✗ starting left_max / right_max at 0 (her on-screen bug; fails on [2, 0, 2])
✗ adding water before updating the max (can go negative)
✗ using the nearest taller bar instead of the tallest
✗ forgetting to subtract the bar's own height
✗ using only the left running max for every index (overcounts near the right end)

test it yourself (paste under either solution above)

s = Solution()
print(s.trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))   # 6
print(s.trap([4, 2, 0, 3, 2, 5]))                     # 9
print(s.trap([3, 0, 2, 0, 4]))                        # 7
print(s.trap([2, 0, 2]))                              # 2
print(s.trap([1, 2, 3, 4]))                           # 0 (no dip)
print(s.trap([5]))                                    # 0

Based on this video: Trapping Rain Water | Two Pointers

i	height[i]	left_max (0..i)	right_max (i..11)	level = min	water here	total
0	0	0	3	0	0	0
1	1	1	3	1	0	0
2	0	1	3	1	1	1
3	2	2	3	2	0	1
4	1	2	3	2	1	2
5	0	2	3	2	2	4
6	1	2	3	2	1	5
7	3	3	3	3	0	5
8	2	3	2	2	0	5
9	1	3	2	2	1	6
10	2	3	2	2	0	6
11	1	3	1	1	0	6

i	height[i]	left_max (0..i)	right_max (i..11)	level = min	water here	total
0	0	0	3	0	0	0
1	1	1	3	1	0	0
2	0	1	3	1	1	1
3	2	2	3	2	0	1
4	1	2	3	2	1	2
5	0	2	3	2	2	4
6	1	2	3	2	1	5
7	3	3	3	3	0	5
8	2	3	2	2	0	5
9	1	3	2	2	1	6
10	2	3	2	2	0	6
11	1	3	1	1	0	6

i	height[i]	left_max (0..i)	right_max (i..11)	level = min	water here	total
0	0	0	3	0	0	0
1	1	1	3	1	0	0
2	0	1	3	1	1	1
3	2	2	3	2	0	1
4	1	2	3	2	1	2
5	0	2	3	2	2	4
6	1	2	3	2	1	5
7	3	3	3	3	0	5
8	2	3	2	2	0	5
9	1	3	2	2	1	6
10	2	3	2	2	0	6
11	1	3	1	1	0	6