Trapping Rain Water
Trapping Rain Water
Given n non-negative integers representing the height of bars in a histogram (each bar has width 1), compute how much water can be trapped after raining. Water trapped above a bar at index i = min(maxLeft[i], maxRight[i]) - height[i], where maxLeft[i] is the tallest bar to the left and maxRight[i] is the tallest bar to the right. Your solve(...) function receives these inputs directly as ready-made arguments — no input reading or parsing needed. Just compute and return the answer. Example: n=12, heights=[0 1 0 2 1 0 1 3 2 1 2 1] → 6
Input format — only if your code reads from stdin
Input format (stdin): - First line: integer n (number of bars) - Second line: n space-separated non-negative integers (heights) Output: a single integer — the total units of water trapped.
Approach
Two-pointer approach (O(n) time, O(1) space): maintain left and right pointers plus leftMax and rightMax. If leftMax ≤ rightMax, process left (water = leftMax - h[left], advance left). Otherwise process right (water = rightMax - h[right], advance right).
Input
Output
- •
1 ≤ n ≤ 2×10^4, 0 ≤ height[i] ≤ 10^5
More Arrays problems
Browse all coding problems →Press Run to test your custom input, or Submit to judge against all test cases.
Sign in to continue
Create a free account to run code, submit solutions and track progress.
- Free forever — no credit card
- 10+ languages with live execution
- Points, streaks & leaderboards