BL
U

49. Trapping Rain Water

Med.

Problem Description

Given an array of NN non-negative integers representing an elevation map where each bar has width 1, compute how many total units of water can be trapped after raining.

Input Format

  • •Line 1: An integer NN (1≤N≤1051 \le N \le 10^5).
  • •Line 2: NN space-separated non-negative integers A1,…,ANA_1, \dots, A_N.

Output Format

Print the total units of trapped water.

Example 1:
Input:
12
0 1 0 2 1 0 1 3 2 1 2 1
Output:
6
Explanation: Classic trapping rain water elevation map traps 6 units of water.
Example 2:
Input:
6
4 2 0 3 2 5
Output:
9
Explanation: Water trapped in valleys equals 9.
Example 3:
Input:
3
3 2 1
Output:
0
Explanation: Monotonically decreasing bars trap 0 water.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online