In this tutorial we will learn about Rain Water Trapping Problem with some examples. This is a part of Data Structure.
What is Rain Water Trapping Problem in Data Structure?
In simple way, we have many building placed left and right to each other. All buildings have different heights as shown in above image.
We have to put water inside the builds area then calculate that part is the problem.
This problem is solved by using JavaScript. The approach will same for all programming language. There are many way to solve the problem, from them we picked one which has less time complexity and Auxiliary space.
Approach 1
This is best approach for this problem. While loop is used to iterate the array. At every index, the amount or rainwater stored is the difference between the current index height and a minimum or left maximum height and right maximum height.
Time Complexity: O(N)
Auxiliary Space: O(1)
function maxWater(arr, n)
{
// indicates to traverse the array
let left_value = 0;
let right_value = n - 1;
let left_max = 0;
let right_max = 0;
let result = 0;
while (left_value <= right_value)
{
if(right_max <= left_max)
{
result += Math.max(0, right_max - arr[right_value]);
right_max = Math.max(right_max, arr[right_value]);
right_value --;
}
else
{
result += Math.max(0, left_max - arr[left_value]);
left_max = Math.max(left_max, arr[left_value]);
left_value ++;
}
}
return result;
}
// Driver code
let arr = [5, 8, 4, 3, 7, 4];
let N = arr.length;
document.write(maxWater(arr, N));
Answer : 7
Call the above function and pass the source array and the length of the array.
This problem is solved using JavaScript. The functionality is same for all languages, only the way of declaring variables and array is different. See other examples.
Thank you for visiting tutorial on FlutterTPoint. For any issue and doubts you can comment in the comment section below.