Two Pointers
Keep the widest container and move only the wall that limits the water.
0 of 3 problems solved
Two Pointers
Keep the widest container and move only the wall that limits the water.
- •Is the shorter wall limiting the area?
- •Should I keep the widest window first?
- •Am I moving the shorter side only?
Think of each number as the height of a wall. Pick one wall on the left and one on the right, and those two walls make a container. The water you can hold depends on two things: how far apart the walls are and which wall is shorter. The shorter wall is the boss here. That is why, after checking an area, you only move the shorter side and hope to find a taller wall.
The shorter wall is the bottleneck. Moving the taller wall cannot help until the shorter wall improves.
- 1Start with one pointer at the far left and one at the far right.
- 2Compute the current area using width times the shorter wall.
- 3Save the best area seen so far.
- 4Move the pointer that points to the shorter wall.
- 5Repeat until the pointers meet.
Moving the taller wall feels fair, but it cannot raise the water level because the shorter wall is still limiting everything.
Move Zeroes
Two-pointer write-scan: write pointer tracks the next non-zero slot, read pointer scans ahead. Fill the remaining tail with zeros afterward.
Trapping Rain Water
Left and right pointers converge inward. The side with the smaller max height is the bottleneck — water there equals that max minus the current bar height.