Rain Water Trapping Problem Statement

Given an array/list ARR of size N, representing an elevation map where each element ARR[i] denotes the elevation of the i-th bar. Your task is to calculate and print the total amount of rainwater that can be trapped between these elevations.

Example:

Input:

T = 1 N = 6 ARR = [0,1,0,2,1,0,1,3,2,1,2,1]

Output:

6

Explanation:

The elevation map is represented by array ARR, and 6 units of rainwater can be trapped between these elevations.

Constraints:

1

Question

Rain Water Trapping Problem Statement

Given an array/list ARR of size N, representing an elevation map where each element ARR[i] denotes the elevation of the i-th bar. Your task is to calculate and print the total amount of rainwater that can be trapped between these elevations.

Example:

Input:

T = 1
N = 6
ARR = [0,1,0,2,1,0,1,3,2,1,2,1]

Output:

Explanation:

The elevation map is represented by array ARR, and 6 units of rainwater can be trapped between these elevations.

Constraints:

1 <= T <= 10
0 <= N <= 10⁴
0 <= ARR[i] <= 10⁹
Time Limit: 1 second

Note:

The width of each bar is the same and is equal to 1. You are not required to print anything; it has already been taken care of. Just implement the function to calculate the trapped water.

Accepted Answer

Calculate the total amount of rainwater that can be trapped between given elevations in an array.

Use two-pointer approach to keep track of left and right boundaries.
Calculate the trapped water by finding the minimum of maximum heights on left and right sides for each bar.
Sum up the trapped water for all bars to get the total amount of rainwater trapped.

Asked in Samsung