Trapped Rainwater

Given an array of non-negative integers representing the heights of buckets arranged in a line, your task is to determine the total amount of water that can be trapped between them after a rainfall.

The water trapped at any position is computed as the minimum of the maximum heights to its left and right minus the height at that position. Formally, for each index i, if the maximum height to the left is \(L_i\) and to the right is \(R_i\), then the water trapped at index i is \(\max(0, \min(L_i, R_i) - height[i])\). Your solution should efficiently compute the overall trapped water using optimal algorithms such as dynamic programming or two-pointer techniques.

For example, if the input heights are [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], the trapped water is 6.

inputFormat

The first line of input contains an integer n denoting the number of buckets. If n > 0, the second line contains n space-separated non-negative integers representing the heights of each bucket.

outputFormat

Output a single integer which is the total amount of water that can be trapped between the buckets.

12
0 1 0 2 1 0 1 3 2 1 2 1

6