Trapping Rain Water — Hard Coding Interview Question

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.

Example

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

Output: 6

Constraints

• n == height.length
• 1 ≤ n ≤ 2 × 10⁴
• 0 ≤ height[i] ≤ 10⁵

Topics & Companies

Topics: arrays, two-pointers

Asked by: Amazon, Google, Meta, Microsoft, Apple, Bloomberg

Optimal Solution Complexity

Time complexity: O(n). Space complexity: O(1).

Practice more

• All DSA Problems
• DSA Patterns