{"post":"

Trapping rain water problem

Input: [1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Explanation: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can be trapped after raining.
\nThe above problem statement can be a bit perplexing – so see the below picture for reference.

$\"\"$

Each square of water trapped is 1 unit.

Instead of directly aiming for Efficient Solution, we aim for a solution firsthand. To quote Donald Knuth, the great computer scientist “Premature Optimization is the root for all evil”.

This problem has 3 main approaches. But firstly, we see the brute force approach, and then we go on improving some bits and parts of our code.

# Brute Force

Herein, we simply aim for the solution, no matter the cost. So, devising a pseudo code for this:

Maintain two indices, one to iterate on the length of elevation or tower at the index, and other to calculate the water at a particular index.
Iterate till length :
\na. Store the max length of the buildings to the left and to the right of the index.
\nb. The shorter of the two is taken as the level till which the water can rise.
\nc. Decrease the height of the building at current index
Summation of water collected at all indices gives us the total water.

Code:

#include <iostream>\n#include <algorithm>\nusing namespace std;\nvoid bruteForceRainwater(int buildingArray[], int size)\n{\n\tif (size == 1 || size == 0)\n\t{\n\t\tcout << \"Sorry\";\n\t\treturn;\n\t}\n\tint index, waterAtCurrent, totalWater = 0;\n\tfor (index = 1; index < size - 1; index++)\t// as will iterate till second last, water can never be stored at the first and the last\n\t{\n\t\tint left = buildingArray[index];\n\t\tfor (int j = 0; j < index; j++)\n\t\t\tleft = max(left, buildingArray[j]);\n\t// Find the maximum element on its right\n\tint right = buildingArray[index];\n\tfor (int j = index + 1; j &lt; size; j++)\n\t\tright = max(right, buildingArray[j]);\n\tint waterLevel = (min(left, right)) - buildingArray[index];\n\tif (waterLevel &gt;= 0)\n\t\twaterAtCurrent = waterLevel;\n\telse\n\t\twaterAtCurrent = 0;\n\ttotalWater += waterAtCurrent;\n}\ncout &lt;&lt; \"Total Water is :\";\ncout &lt;&lt; totalWater;\n
\n}\nint main()\n{\nint buildings[] = { 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };\nbruteForceRainwater(buildings, 11);\nreturn 0;\n}

Time complexity : O(n2).
\nSpace complexity: O(1)

# Improvement on Time Complexity

We try to reduce the time complexity here.

Code:

#include <iostream>\n#include <algorithm>\nusing namespace std;\nvoid reduceTimeRainwater(int buildingArray[], int size)\n{\nif (size == 1 || size == 0)\n{\ncout << \"Sorry\";\nreturn;\n}\nint index, waterAtCurrent, totalWater = 0;\nint leftArray[size], rightArray[size];\nleftArray[0] = buildingArray[0];\nfor (int i = 1; i < size; i++)\nleftArray[i] = max(leftArray[i - 1], buildingArray[i]);
\nrightArray[size - 1] = buildingArray[size - 1];\nfor (int i = size - 2; i &gt;= 0; i--)\n\trightArray[i] = max(rightArray[i + 1], buildingArray[i]);\nfor (index = 1; index &lt; size; index++)\n{\n\twaterAtCurrent = min(leftArray[index], rightArray[index]) - buildingArray[index];\n\ttotalWater += waterAtCurrent;\n}\ncout &lt;&lt; \"Total Water is :\" &lt;&lt; totalWater;\n
\n}
\nint main()\n{\nint buildings[] = { 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };\nreduceTimeRainwater(buildings, 11);\nreturn 0;\n}

Time complexity: O(n)
\nSpace complexity: O(n)

# Decreasing the auxiliary space required

This is the most efficient solution, with us minimizing the spacing required by our program.
\nCode:

#include <iostream>\nusing namespace std;\nint findWater(int buildingArray[], int n)\n{\n\tint totalWater = 0;\n\tint left = 0, right = 0;\n\tint low = 0, high = n - 1;\nwhighle(low &lt;= high)\n{\n\tif (buildingArray[low] &lt; buildingArray[high])\n\t{\n\t\tif (buildingArray[low] &gt; left)\n\t\t\t// update max in left\n\t\t\tleft = buildingArray[low];\n\t\telse\n\t\t\ttotalWater += left - buildingArray[low];\n\t\tlow++;\n\t}\n\telse\n\t{\n\t\tif (buildingArray[high] &gt; right)\n\t\t\t// update right maximum\n\t\t\tright = buildingArray[high];\n\t\telse\n\t\t\ttotalWater += right - buildingArray[high];\n\t\thigh--;\n\t}\n}\ncout &lt;&lt; \"Total Water is \" &lt;&lt; totalWater;\n
\n}
\nint main()\n{\nint[] buildings = { 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
\noptimizedSpaceRainwater(buildings, 11);\n
\n}

Time complexity :O(n)
\nSpace complexity :O(1)

Output :

Total Water is: 6

This is how we solve the trapping rainwater problem.

\n","title":"Trapping rain water problem","authorDetails":{"name":"Anshuman Raina","slug":"anshuman-raina"},"seo":{"title":"Trapping rain water problem"},"description":"Trapping rain water problem explanation and solution with and without extra space in O(n) time complexity.","slug":"rainwater-trapping-problem/","articleId":"636a83447bb1ce5072622b90","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}