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?

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

For [1, 8, 6, 2, 5, 4, 8, 3, 7]:

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

Trapping Rain Water looks different because the answer is the sum of many small amounts, not one best pair. Yet it relies on the same idea of limiting boundaries.

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]

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

Maintain:

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

If leftMax <= rightMax, the right side already has a wall at least as tall as leftMax. For the current left position, no unseen wall on the right can make the limiting boundary lower than leftMax. Its water can therefore be finalized using leftMax.

The symmetric argument applies when rightMax < leftMax.

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]

from left, leftMax becomes 3
height 0 sits below leftMax by 3
height 2 sits below leftMax by 1
height 0 sits below leftMax by 3
right boundary 4 confirms the left maximum is the limiting side
total = 3 + 1 + 3 = 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 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.

When explaining a movement rule, state:

1. the current candidate’s limiting quantity;
2. why one possible movement cannot improve it;
3. why the chosen movement is the only remaining chance for improvement or finalization.

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