Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

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

Advancing the taller side first (wrong limiting wall).
Forgetting water is 0 when height equals the current side max.
Stack version: width is i - left - 1, not i - mid.

Reflection

Which cue made you pick two pointers vs stack in under 90 seconds?
What input breaks a wrong “only look left” invariant?
Can you derive the O(1) two-pointer rule from the min(leftMax, rightMax) formula?