Frontend Prep

Appearance

Frequently Asked at Uber — This problem has been reported multiple times in recent Uber L5A interviews.

Trapping Rain Water ​

Problem Statement ​

Given n non-negative integers representing an elevation map where each bar has width 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The pools of water above the bars total 6 units.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

  • 1 <= n <= 2 * 10^4
  • 0 <= height[i] <= 10^5

Difficulty: Hard

Pattern Recognition ​

  • What is the structure of the input? A 1D array of heights.
  • What are we computing? Total trapped water — a per-index computation: water[i] = max(0, min(maxLeft[i], maxRight[i]) - height[i]).
  • What pattern does this suggest? Two-pointer sweep. Less memory-intensive than prefix arrays.
  • Why does this pattern fit? At any index, the trapped water depends only on the maximum heights to its left and right. Two pointers let you compute both maxes incrementally and commit to water amounts on the fly.

Approach ​

Brute Force — For each bar, scan left and right ​

For each index i, find maxLeft and maxRight by scanning both halves. Water at i = min(maxLeft, maxRight) - height[i].

Time: O(N^2). Space: O(1). Why insufficient: N up to 20000 makes it 4 * 10^8 ops — too slow.

Better — Prefix Max Arrays ​

Precompute leftMax[i] and rightMax[i] in linear time. Sum min(leftMax[i], rightMax[i]) - height[i].

Time: O(N). Space: O(N). Works, but the next step halves the space.

Optimal — Two Pointers ​

Key Insight: At each step, whichever side (left or right) has the smaller current height is the bottleneck — you can commit water for that side without needing to know exactly what's on the other side, because the other side is guaranteed to be at least as tall.

Step-by-step:

  1. left = 0, right = n-1, leftMax = rightMax = 0, water = 0.
  2. While left < right:
    • If height[left] < height[right]: the left side is the bottleneck.
      • Update leftMax = max(leftMax, height[left]).
      • Add leftMax - height[left] to water.
      • Advance left.
    • Else symmetrically for the right side.
  3. Return water.

Time: O(N). Space: O(1).

Walkthrough ​

height = [0,1,0,2,1,0,1,3,2,1,2,1]

Stepleftrighth[l]h[r]leftMaxrightMaxaddwater
1011010000
2111111000
3211011011
4311212001
5310222001
639212212
738222202
837232202
947132213
1057032225
1167132216
1277—————6

Answer: 6.

Implementation ​

typescript
function trap(height: number[]): number {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0, water = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left];
      left++;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right];
      right--;
    }
  }
  return water;
}
cpp
class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0, water = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                leftMax = max(leftMax, height[left]);
                water += leftMax - height[left];
                left++;
            } else {
                rightMax = max(rightMax, height[right]);
                water += rightMax - height[right];
                right--;
            }
        }
        return water;
    }
};

Watch out: Updating leftMax before adding to water. If you add first, you subtract the old max from a taller current bar and get negative water.

Watch out: The strict vs non-strict comparison < / <= doesn't actually matter for correctness, but pick one and stay consistent to avoid off-by-one confusion.

Watch out: Explain why you can commit water for the shorter side. Interviewers love the "bounded by smaller max" argument — saying "because it's smaller" without the proof loses points.

Complexity Analysis ​

TimeSpace
Brute ForceO(N^2)O(1)
Prefix ArraysO(N)O(N)
Two PointersO(N)O(1)

Bottleneck: You must see every bar at least once — O(N) is a hard lower bound.

Edge Cases ​

  1. Monotonic array [1,2,3,4] — No water anywhere.
  2. Single peak [0,1,0] — Still no water; need two higher bars flanking a dip.
  3. All zeros — 0 water.
  4. Length 1 or 2 — No water.
  5. Plateaus [3,3,0,3] — Water = 3 in the middle cell.
  • LC 407 — Trapping Rain Water II: 2D version. Uses a min-heap expanding from the border inward.
  • LC 11 — Container With Most Water: Two-pointer with a different metric (area between two bars).
  • LC 84 — Largest Rectangle in Histogram: Monotonic stack on bar heights.
  • LC 238 — Product of Array Except Self: Prefix-from-both-sides technique.

Edge Cases Recap & Algorithmic Notes ​

The two-pointer approach works because of the invariant: when height[left] < height[right], every bar between has some bound on the right that is at least height[right] >= height[left], so leftMax is the binding constraint. This "move the smaller side inward" argument is the reason you can commit water without seeing the rest of the array.

What Is Expected at Each Level? ​

Junior / New Grad: Get the O(N) prefix-array solution with a clean explanation. May need help seeing how two pointers remove the prefix arrays.

Mid-level: Write two-pointer solution immediately. Justify why you can commit water on the smaller side. Handle all edge cases.

Senior: Proactively contrast all three approaches, note the invariant in a single sentence, and extend to 2D (LC 407) with a heap. Discuss streaming: if heights arrive online, what can you precompute?

Frontend interview preparation reference.