🔗 LeetCode🔗 Neetcode

Trapping Rain Water

Hard★ Premiumtwo pointersAmazonGoogleGoldman SachsMicrosoft

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

Examples

Input:height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output:6
Explanation:The elevation map [0,1,0,2,1,0,1,3,2,1,2,1] can trap 6 units of rain water.
Input:height = [4,2,0,3,2,5]
Output:9

Constraints

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

💡 Hints

Hint 1

Water at any index depends on the min of max-left and max-right heights.

Hint 2

Use two pointers from both ends, tracking leftMax and rightMax.

Hint 3

If height[left] < height[right], process left side; otherwise process right.

Algorithm Complexity

Official asymptotic Big-O runtime and auxiliary memory analysis

Linear
Algorithmic Approach

Two pointers from both ends. The side with the smaller height determines the water level. Track leftMax/rightMax — if current height is less than the max, water is trapped.

Time ComplexityO(n)
Why:

Two pointers move inward from left and right boundaries, calculating trapped water on the lower elevation in a single pass.

Space ComplexityO(1)
Why:

Requires only constant scalar variables (left, right, leftMax, rightMax) without precomputed prefix arrays.

Big-O Growth CurveLinear (O(N))
Execution time scales directly in proportion to the input size.

🌍 Real-World Use Cases

Civil EngineeringVolume estimation

Estimating water pooling volume on terrain based on elevation profiles — same min-boundary logic as this problem.

★ Premium Challenge

Trapping Rain Water is classified as a premium problem.

Client-Side Architecture Preview (Phase 3 Sprint 3)
This gating is an honest client-side architecture preview. True secure server entitlements, user database roles, and payment verification will be introduced in Phase 4 with the PostgreSQL backend. There is no fake checkout or simulated payment processing.
Difficulty: HardPattern: two-pointersCompanies: Amazon, Google, Goldman Sachs