Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Two Pointers

Guide 5 of 6 · Path 5 of 6

← PreviousNext →

Interactive

Mental model

A worked animation for this problem. Scrub steps or press space to pause; re-tell the invariant out loud.

Step 1 of 8
1
2
3
4
7
11

L = 0, R = n-1

Sorted array. Find a pair that sums to target 9.

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Hardtwo-pointersmonotonic-stack

Trapping Rain Water

Problem (restated)

Given non-negative elevation heights, compute how much water can be trapped after raining. Water sits above each index up to the lower of the tallest bars on its left and right.

Intuition

Water at index i equals min(leftMax[i], rightMax[i]) - height[i] (or 0 if negative). You can precompute both max arrays in O(n) space, or compute the same idea online with two pointers (O(1) space) or a monotonic stack (O(n) space, natural if you already think in “next greater wall”).

Approaches

Two pointers with max heights

Tested only
Time O(n)Space O(1)

Idea. Maintain leftMax / rightMax while walking from both ends. Always advance the side with the smaller current height: that side’s max is the limiting wall for water at that index.

Walkthrough. [0,1,0,2,1,0,1,3,2,1,2,1]. When the left side is lower, water uses leftMax; when the right is lower, water uses rightMax. Total fills to 6.

Trade-offs. Optimal space. Slightly harder to invent under pressure than the two-array DP, but interview gold when they ask for O(1) extra memory.

Solution
export function trap(height: number[]): number {
  let lo = 0, hi = height.length - 1;
  let leftMax = 0, rightMax = 0, water = 0;
  while (lo <= hi) {
    if (height[lo]! <= height[hi]!) {
      if (height[lo]! >= leftMax) leftMax = height[lo]!;
      else water += leftMax - height[lo]!;
      lo++;
    } else {
      if (height[hi]! >= rightMax) rightMax = height[hi]!;
      else water += rightMax - height[hi]!;
      hi--;
    }
  }
  return water;
}

export function trap(height: number[]): number {
  let lo = 0, hi = height.length - 1;
  let leftMax = 0, rightMax = 0, water = 0;
  while (lo <= hi) {
    if (height[lo]! <= height[hi]!) {
      if (height[lo]! >= leftMax) leftMax = height[lo]!;
      else water += leftMax - height[lo]!;
      lo++;
    } else {
      if (height[hi]! >= rightMax) rightMax = height[hi]!;
      else water += rightMax - height[hi]!;
      hi--;
    }
  }
  return water;
}

Monotonic stack

Tested only
Time O(n)Space O(n)

Idea. Keep a decreasing stack of indices. When a taller bar arrives, pop the valley and trap a horizontal slab between the new bar and the new stack top: height = min(leftWall, rightWall), mid, width = gap between walls.

Walkthrough. Same array: each pop fills one “layer” of water over a segment. Sum of slabs is still 6.

Trade-offs. Clear geometric story; uses O(n) stack. Prefer when the problem already smells like next-greater / histogram (and you know monotonic stack). Two pointers wins on space.

Solution
/** Monotonic decreasing stack of indices; pop to trap water between walls. */
export function trapStack(height: number[]): number {
  const st: number[] = [];
  let water = 0;
  for (let i = 0; i < height.length; i++) {
    while (st.length && height[i]! > height[st[st.length - 1]!]!) {
      const mid = st.pop()!;
      if (!st.length) break;
      const left = st[st.length - 1]!;
      const h = Math.min(height[left]!, height[i]!) - height[mid]!;
      const w = i - left - 1;
      water += h * w;
    }
    st.push(i);
  }
  return water;
}

/** Monotonic decreasing stack of indices; pop to trap water between walls. */
export function trapStack(height: number[]): number {
  const st: number[] = [];
  let water = 0;
  for (let i = 0; i < height.length; i++) {
    while (st.length && height[i]! > height[st[st.length - 1]!]!) {
      const mid = st.pop()!;
      if (!st.length) break;
      const left = st[st.length - 1]!;
      const h = Math.min(height[left]!, height[i]!) - height[mid]!;
      const w = i - left - 1;
      water += h * w;
    }
    st.push(i);
  }
  return water;
}

Template connection

Primary pattern here is two pointers (opposite ends). The stack version is the monotonic stack next-greater cousin of largest rectangle / daily temperatures.

Common bugs

Reflection