Trapping Rainwater Problem Statement

You are given an array ARR of long type, which represents an elevation map where ARR[i] denotes the elevation of the i^th bar. Calculate the total amount of rainwater that can be trapped within these elevations.

Input:

The first line contains an integer 'T', denoting the number of test cases. Each test case consists of two lines. The first line contains an integer 'N', representing the size of the array. The second line contains 'N' single space-separated integers, representing the elevation of the bars.

Output:

For each test case, output a single integer in a new line, indicating the total water that can be trapped.

Example:

Input:

2 6 0 2 1 3 0 1 5 3 0 2 0 4

Output:

4 7

Constraints:

1 ≤ T ≤ 10

0 ≤ N ≤ 10⁴

0 ≤ ARR[i] ≤ 10⁹

Time Limit: 1 sec

Note:

The width of each bar is uniform and equals 1.

Question

Trapping Rainwater Problem Statement

You are given an array ARR of long type, which represents an elevation map where ARR[i] denotes the elevation of the i^th bar. Calculate the total amount of rainwater that can be trapped within these elevations.

Input:

The first line contains an integer 'T', denoting the number of test cases. Each test case consists of two lines. The first line contains an integer 'N', representing the size of the array. The second line contains 'N' single space-separated integers, representing the elevation of the bars.

Output:

For each test case, output a single integer in a new line, indicating the total water that can be trapped.

Example:

Input:

2
6
0 2 1 3 0 1
5
3 0 2 0 4

Output:

4
7

Constraints:

1 ≤ T ≤ 10
0 ≤ N ≤ 10⁴
0 ≤ ARR[i] ≤ 10⁹
Time Limit: 1 sec

Note:

The width of each bar is uniform and equals 1.

Accepted Answer

Calculate the total amount of rainwater that can be trapped within given elevation map.

Iterate through the array to find the maximum height on the left and right of each bar.
Calculate the amount of water that can be trapped above each bar by taking the minimum of the maximum heights on the left and right.
Sum up the trapped water above each bar to get the total trapped water for the elevation map.

Accepted Answer

At any index i, the amount of water that can be trapped is:
min(maxLeft, maxRight) - ARR[i]
maxLeft is the tallest bar on the left of index i
maxRight is the tallest bar on the right of index i
one can use two pointers (left and right) and move inward, tracking the maxLeft and maxRight as we go