Choosing Which Pointer Moves

Movement needs a reason

The previous reading used sorted values: a sum that was too small or too large told us which side could no longer participate in an answer. Some two-pointer problems are not sorted. Movement is still possible, but a different fact must make it safe.

The recurring question is:

What limits the current candidate, and which movement could possibly improve that limit?

This is a better starting point than memorizing “move the shorter line” or “process the smaller side.” Those rules become easy to reconstruct after the limiting quantity is clear.

Two Pointers Without Sorting: Container With Most Water

Why introduce a water-container problem here? In the previous reading, sorted order let us rule out pairs without checking each one. The important idea was safe elimination, not merely placing pointers at opposite ends. This example teaches the same idea when the array is not sorted: we will use a limit on the possible area to rule out pairs.

First, understand what we are choosing. In Container With Most Water, each array value is the height of a vertical wall at that index. Adjacent indices are one unit apart. Choose any two walls, with the ground as the bottom, to form a container. The goal is to choose the pair that holds the most water, measured as a two-dimensional area. Only the two chosen walls determine this area; walls between them do not subtract space from it.

The pointers identify our chosen walls: left is the left wall’s index, and right is the right wall’s index. Their distance gives the width. The water can rise only as high as the shorter wall, because it would spill over that side. That gives us:

width  = right - left
height = min(heights[left], heights[right])
area   = width × height

We could calculate this for every pair, taking quadratic time. The two-pointer question is whether inspecting one pair can tell us which other pairs cannot beat it. Do not sort the heights: that would change the walls’ positions and therefore the widths.

Why begin at the two ends?

We know how to measure one container, but we still need to choose which pairs to test. If we start with two nearby walls, there may be better pairs on either side, and we have no simple way to rule them out. What does starting with the two outermost walls give us that a pair in the middle does not?

Starting at the outermost lines gives the largest possible width. Every inward movement makes the width smaller. A later container can beat the current area only if it gains enough height to compensate for that lost width.

Suppose the left line is shorter:

left height = 3
right height = 8

If you move only the right pointer inward, the width decreases while the container height can never exceed 3; the unchanged left line still limits it. That move cannot produce a larger area than the current pair.

Moving the shorter left pointer is the only move with a chance to find a taller limiting line. It does not guarantee improvement, but it preserves every possibility that could improve.

function maxArea(heights: number[]): number {
  let left = 0
  let right = heights.length - 1
  let best = 0

  while (left < right) {
    const width = right - left
    const height = Math.min(heights[left], heights[right])
    best = Math.max(best, width * height)

    if (heights[left] <= heights[right]) left += 1
    else right -= 1
  }

  return best
}

When both heights are equal, either side can move. Keeping both cannot increase the width, and any better answer must replace at least one of them.

Predict and Try a Pointer Move

Before reading the longer trace, try this smaller example. A wrong prediction is useful: read which pairs it would keep and why those pairs cannot improve the area. Then make the next decision yourself. The explorer is practice, not a scored exercise.

Worked trace

Goal: Choose two lines from heights [1, 8, 6, 2, 5, 4, 8, 3, 7] that hold the largest container area. Return that area, not a sum of heights or water at each position.

Follow which shorter boundary is discarded and whether the best area improves. left and right below are indices; heights gives the two values at those indices. These are the first four comparisons, not the complete scan:

left  right  heights  width  area  best  movement
0     8      1,7      8      8     8    left is shorter → left++
1     8      8,7      7     49    49    right is shorter → right--
1     7      8,3      6     18    49    right is shorter → right--
1     6      8,8      5     40    49    equal → move either side

The scan continues until the pointers meet, but 49 remains the maximum. Each discarded boundary has been paired with the farthest possible opposite boundary. If it was the bottleneck there, reducing width while retaining it could not help.

Trapping Rain Water: Measure Water Above Each Position

The container problem chose two lines and ignored the lines between them. Trapping Rain Water changes the task: every height now describes a solid bar of width one, and we want the total water left in the gaps after rain. We do not choose one container; we add the water above every position. Water escapes wherever no wall holds it in.

For heights [3, 0, 2], the middle bar has height zero. The walls beside it have heights 3 and 2, so it holds two units of water. A third unit would spill over the right wall. The outer bars hold none, making the total two.

This connects to the previous problem through the shorter limiting boundary, but the boundary may now be farther away than the neighboring bar. To measure water at one position, first find the tallest wall on each side, then subtract the height of the solid bar occupying that position.

Water above index i is bounded by the tallest wall to its left and the tallest wall to its right:

waterAtI = min(tallestLeft, tallestRight) - height[i]

In this formula, each side’s maximum includes the current bar. The water level is therefore never below the bar itself, and the contribution cannot be negative.

If the shorter surrounding wall has height 4, a wall of height 10 on the other side cannot raise the water above 4. The shorter boundary settles the water level.

A straightforward solution builds two arrays:

• leftMax[i]: tallest wall from the start through i;
• rightMax[i]: tallest wall from i through the end.

That takes O(n) time and O(n) extra space. The two-pointer version keeps only the maximum seen from each side.

Processing the side whose known maximum is smaller

The two arrays above would tell us both surrounding maxima at every position. Suppose we want to avoid storing those arrays. We can scan inward while remembering the tallest wall encountered from each end—but then we do not yet know every wall in the middle. How could that partial knowledge be enough to measure any water safely?

Consider an unprocessed bar of height 1. We have already seen a wall of height 3 on its left and a wall of height 4 on its right. If there is no taller left wall between the known wall and this bar, the bar holds exactly 3 - 1 = 2 units. Finding an even taller wall farther to the right cannot change that: the left wall still limits the water level. This is why we process the next bar beside the smaller known maximum, where we know all the walls on that side already.

The two remembered values are:

leftMax  = tallest wall encountered from the left
rightMax = tallest wall encountered from the right

If leftMax <= rightMax, inspect the next bar at left. If it is below leftMax, the known right wall is tall enough to hold water up to leftMax, so add the difference. If the new bar reaches or exceeds leftMax, it holds no water: update the left maximum to include it. Even if this new bar is taller than the known right wall, adding zero is correct because no earlier left wall rises above it.

When rightMax is smaller, do the same from the right. Initially both maxima are zero; processing an outer bar establishes a boundary and adds no water. Notice that we choose the side using the remembered maxima, not simply the two current bar heights.

function trap(heights: number[]): number {
  let left = 0
  let right = heights.length - 1
  let leftMax = 0
  let rightMax = 0
  let total = 0

  while (left <= right) {
    if (leftMax <= rightMax) {
      leftMax = Math.max(leftMax, heights[left])
      total += leftMax - heights[left]
      left += 1
    } else {
      rightMax = Math.max(rightMax, heights[right])
      total += rightMax - heights[right]
      right -= 1
    }
  }

  return total
}

The subtraction is never negative because the maximum is updated to include the current height before water is added.

Small trace: [3, 0, 2, 0, 4]

We want the total water held above these five bars. Follow the actual processing order in the code, including the first visits that establish the two boundary heights. The maxima shown in the table are their values after processing that row.

start: left = 0, right = 4, leftMax = 0, rightMax = 0

side   index  bar  leftMax  rightMax  water added  total
left   0      3    3        0         0            0
right  4      4    3        4         0            0
left   1      0    3        4         3            3
left   2      2    3        4         1            4
left   3      0    3        4         3            7

left = 4, right = 3 → no unprocessed bars remain → return 7

The full algorithm may alternate sides on other inputs. It processes a position only when the opposite known maximum proves that the selected side is the limiting boundary.

Complexity and proof checklist

Both water problems began with many possible boundaries. We avoided repeating that work, but in different ways: the container scan discarded pairs that could not improve the best area; the rain-water scan settled the contribution of one bar at a time. How much work remains once each movement leaves a position behind permanently?

Both algorithms move left rightward or right leftward on every iteration. No position is processed more than once, so they take O(n) time and O(1) auxiliary space.

For the container problem, explain:

1. the current candidate’s limiting quantity;
2. why one possible movement cannot improve it;
3. why replacing the shorter boundary preserves any chance of improvement.

For trapped water, ask a different question: which known wall on the opposite side lets us settle this bar’s contribution without seeing the remaining middle? We are not trying to improve one container; we are adding separate, final water amounts.

That explanation is the algorithm. The if statement is only its translation into code.