{"id":2507,"date":"2023-07-25T13:44:04","date_gmt":"2023-07-25T08:14:04","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2507"},"modified":"2023-07-25T13:44:05","modified_gmt":"2023-07-25T08:14:05","slug":"trapping-rain-water","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/trapping-rain-water\/","title":{"rendered":"Trapping Rain Water"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#algorithm\">Algorithm<\/a><\/li><li><a href=\"#bruteforce-approach\">Bruteforce&nbsp;Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#algorithm\">Algorithm<\/a><\/li><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#java-code-implementation\">Java Code Implementation<\/a><\/li><li><a href=\"#-python-code-implementation\"><meta charset=\"utf-8\">Python Code Implementation<\/a><\/li><\/ul><li><a href=\"#dynamic-programming-approach\">Dynamic Programming Approach<\/a><\/li><li><a href=\"#algorithm\">Algorithm:<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#-java-code-implementation\"><meta charset=\"utf-8\">Java Code Implementation<\/a><\/li><li><a href=\"#-python-code-implementation\"><meta charset=\"utf-8\">Python Code Implementation<\/a><\/li><\/ul><li><a href=\"#approach-3-using-stacks\">Approach 3: Using stacks<\/a><\/li><li><a href=\"#algorithm\">Algorithm:<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#-java-code-implementation\"><meta charset=\"utf-8\">Java Code Implementation<\/a><\/li><li><a href=\"#python-code-implementation\">Python Code Implementation<\/a><\/li><\/ul><li><a href=\"#two-pointers-approach\">Two Pointers Approach<\/a><\/li><li><a href=\"#algorithm\">Algorithm:<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#-java-code-implementation\"><meta charset=\"utf-8\">Java Code Implementation<\/a><\/li><li><a href=\"#-python-code-implementation\"><meta charset=\"utf-8\">Python Code Implementation<\/a><\/li><\/ul><li><a href=\"#practice-problem\">Practice Problem<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-how-many-methods-are-there-to-solve-the-trapping-rainwater-problem\">Q.1: How many methods are there to solve the trapping rainwater problem?<\/a><\/li><li><a href=\"#q2-which-is-the-best-approach-with-respect-to-the-time-and-space-complexity\">Q.2: Which is the best approach with respect to the time and space complexity?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given an integer array A[] consisting of N non-negative integers representing an elevation map, where the width of each bar is 1. The task is to compute the total volume of water that can be trapped after rain.<\/p>\n\n\n\n<p>Examples :<\/p>\n\n\n\n<p><strong>Input:<\/strong> A[] = { 0,1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 }<br><strong>Output:<\/strong> 6<br><strong>Explanation:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"513\"  height=\"210\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-2509 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 513px) 100vw, 513px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/image1-e1633684210692.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/image1-e1633684210692.jpg 513w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/image1-e1633684210692-300x123.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/image1-e1633684210692-380x156.jpg 380w\" ><\/figure>\n\n\n\n<p>The rain water trapped is represented by the blue region.<\/p>\n\n\n\n<ul><li>Trap 1 unit of water between the first and third block<\/li><li>Trap 4 units of water between the second and third blocks.<\/li><\/ul>\n\n\n\n<p>Therefore, the total volume of water is &#8211; 1 + 4 + 1 = 6 units.<\/p>\n\n\n\n<h2 id=\"algorithm\">Algorithm<\/h2>\n\n\n\n<p>The key idea to solve this problem is to understand that rainwater can only be trapped if there exists a block of greater height, both on the left and the right side than the current block. Then rainwater can be trapped on top of the block.<\/p>\n\n\n\n<p>So, it can be easily inferred that the amount of water a block can hold is equal to the minimum of the maximum height present on both the left and right half minus the height of the current block.<\/p>\n\n\n\n<p>i.e.<\/p>\n\n\n\n<p>Vol_of_A[i] = min(right_max, left_max) &#8211; A[i]\n\n\n\n<h2 id=\"bruteforce-approach\">Bruteforce&nbsp;Approach<\/h2>\n\n\n\n<p><br>Since our task is to find the maximum height on the left and right for each element of the array, simply traverse each element of the array A[]. For each element, find the maximum height on the left and the maximum height on the right. At last, add min(right_max, left_max) &#8211; A[i] to answer.<\/p>\n\n\n\n<h3 id=\"algorithm\"><span id=\"algorithm-2\">Algorithm<\/span><\/h3>\n\n\n\n<ul><li>Initialise a variable <strong>res<\/strong> to 0, to store the final answer.<\/li><li>Traverse the array <strong>A[] <\/strong>from <strong>1 <\/strong>to<strong> N <\/strong>and for each element:<ul><li>Initialise <strong>left_max<\/strong> = 0 and <strong>right_max <\/strong>= 0<\/li><li>Traverse from <strong>A[i]<\/strong> till the beginning and update:<ul><li>left_max = max(left_max, A[i])<\/li><\/ul><\/li><li>Similarly, traverse from <strong>A[i]<\/strong> till the end of the array and update:<ul><li>right_max = max(right_max, A[i])<\/li><\/ul><\/li><\/ul><\/li><\/ul>\n\n\n\n<p>Add min(left_max, right_max) &#8211; A[i]&nbsp; to <strong>res<\/strong>.<\/p>\n\n\n\n<h3 id=\"c-code-implementation\"><span id=\"c-code-implementation-2\">C++ Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Solution {\npublic:\n    int trapping_rain_water(vector&lt;int>&amp; A) {\n         \n        int res = 0;\n        for (int i = 1; i &lt; A.size() - 1; i++) {\n            \n            \/\/Find left_max\n            int left_max = INT_MIN;\n            for (int j = i - 1; j >= 0; j--) {\n                left_max = max(left_max, A[j]);\n            }\n\t\t\t\/\/Find right_max\n            int right_max = INT_MIN;\n            for (int k = i + 1; k &lt; A.size(); k++) {\n                right_max = max(right_max, A[k]);\n            }\n\t\t\t\/\/Find volume\n            int maxW = min (left_max,right_max);\n            res += maxW - A[i];\n        }\n        return res;\n    }\n};\n<\/pre>\n\n\n\n<h3 id=\"java-code-implementation\">Java Code Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static int trapping_rain_water(int[] A, int N)\n{\n    int res = 0;\n    for(int i = 0; i &lt; N ; i++)\n    { \n        int left_max= arr[i];\n        for(int j = i - 1; j >= 0; j--)\n        {\n            left_max = Math.max(left_max, A[j]);\n        }\n        int right_max = A[i];\n        for(int j = i + 1; j &lt; n; j++)\n        {\n            right_max = Math.max(right_max, A[j]);\n        }\n        res += Math.min(left_max, right_max) - A[i];\n    }\n    return res;\n}\n<\/pre>\n\n\n\n<h3 id=\"-python-code-implementation\"><span id=\"python-code-implementation\"><meta charset=\"utf-8\">Python Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def trapping_rain_water(A, N) :\n    res = 0;\n    for i in range(1, N - 1) :\n        left_max = A[i];\n        for j in range(i) :\n            left_max = max(left_max, A[j]);\n         \n        right_max = A[i];\n         \n        for j in range(i + 1 , n) :\n            right_max = max(right_max, A[j]);\n        res = res + (min(left_max, right_max) - A[i]);\n \n    return res;<\/pre>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(N^2). For each element, the left and right half are traversed.<\/li><li><strong>Space Complexity:<\/strong> O(1)<\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"dynamic-programming-approach\">Dynamic Programming Approach<\/h2>\n\n\n\n<p>Can we improve the efficiency from O(N^2) to O(N)? Remember, in brute force, we are traversing left and right for each element. What if we store this information, then the problem can be solved using a single traversal, essentially reducing the time complexity to O(N).<\/p>\n\n\n\n<p>The idea is to consider two arrays <strong>left_max[]<\/strong> and <strong>right_max[]<\/strong>, where <strong>left_max[i]<\/strong> will store the maximum height on the left until index <strong>i<\/strong>. Similarly,&nbsp; <strong>right_max[i]<\/strong> will store the maximum height on the right until index <strong>i<\/strong>.<\/p>\n\n\n\n<h2 id=\"algorithm\"><span id=\"algorithm-3\">Algorithm:<\/span><\/h2>\n\n\n\n<ul><li>Initialise two arrays <strong>left_max[]<\/strong> and <strong>right_max[]<\/strong> of size <strong>N.<\/strong><\/li><li>Consider a variable <strong>mx = 0<\/strong>.<\/li><li>Traverse from left to right and for each index <strong>i<\/strong>, update <strong>mx = max(mx, A[i[)<\/strong> and assign <strong>left_max = mx<\/strong>.<\/li><li>Similarly, traverse a loop, <strong>N<\/strong> to <strong>1<\/strong> and for each index <strong>i<\/strong>, update <strong>mx = max(mx, A[i[)<\/strong> and assign <strong>right_max = mx<\/strong>.<\/li><li>Initialise a variable <strong>res = 0<\/strong> and traverse from <strong>0<\/strong> to <strong>N &#8211; 1<\/strong>. For each index <strong>i<\/strong>, add <strong>min(left_max[i], right_max[i]) &#8211; A[i]<\/strong> to <strong>res.<\/strong><\/li><\/ul>\n\n\n\n<h3 id=\"c-code-implementation\"><span id=\"c-code-implementation-3\">C++ Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Solution {\npublic:\n   \n\tint trapping_rain_water(vector&lt;int>&amp; A)\n\t{\n\t\tint res = 0;\n\t\tint N = A.size();\n\t\tint left_max[N], right_max[N];\n\t\tint mx = INT_MIN;\n\t\tfor (int i = 0; i &lt; N; i++) {\n\t\t\tmx = max(mx, A[i]);\n\t\t\tleft_max[i] = mx;\n\t\t}\n\t\tmx = INT_MIN\n\t\tfor (int i = N - 1; i >= 0; i--) {\n\t\t\tmx = max(mx, height[i]);\n\t\t\tright_max[i] = mx\n\t\t}\n\t\tfor (int i = 0; i &lt; N ; i++) {\n\t\t\tres += min(left_max[i], right_max[i]) - A[i];\n\t\t}\n\t\treturn res;\n\t}\n};<\/pre>\n\n\n\n<h3 id=\"-java-code-implementation\"><span id=\"java-code-implementation-2\"><meta charset=\"utf-8\">Java Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public int trapping_rain_water(int[] A) {\n int res = 0;\n if (A.length == 0) {\n   return 0;\n }\n int[] leftMax = new int[A.length];\n\n int[] rightMax = new int[A.length];\n\n leftMax[0] = A[0];\n\n for (int i = 1; i &lt; leftMax.length; i++) {\n   leftMax[i] = Math.max(leftMax[i - 1], A[i]);\n }\n\n rightMax[A.length - 1] = A[A.length - 1];\n\n for (int j = rightMax.length - 2; j >= 0; j--) {\n   rightMax[j] = Math.max(rightMax[j + 1], A[j]);\n }\n for (int x = 0; x &lt; A.length; x++) {\n   res += Math.min(leftMax[x], rightMax[x]) - A[x];\n }\n return res;\n}<\/pre>\n\n\n\n<h3 id=\"-python-code-implementation\"><span id=\"python-code-implementation-2\"><meta charset=\"utf-8\">Python Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def trapping_rain_water(self, A: List[int]) -> int:\n       N = len(A)\n       left_max = N * [0]\n       right_max = N * [0]\n       ans = 0\n       for i in range(N):\n           if i == 0:\n               left_max[i] = Z[i]\n               right_max[N-1-i] = A[n-1-i]\n           else:\n               left_max[i] = max(left_max[i-1], A[i])\n               right_max[n-1-i] = max(right_max[n-i], A[N-1-i])\n              \n       for i in range(N):\n           ans += (min(left_max[i], right_max[i]) - A[i])\n      \n       return ans<\/pre>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(N) + O(N) + O(N) = O(N), since the array is traversed thrice.<\/li><li><strong>Space Complexity:<\/strong> O(N), since two arrays are needed.<\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"approach-3-using-stacks\">Approach 3: Using stacks<\/h2>\n\n\n\n<p>In <strong>DP<\/strong>, the arrays were traversed twice. Can we improve the approach to a single scan? The idea is to keep track of the area between the current block <strong>A[i] <\/strong>and all the previous blocks with smaller heights in the array. We can simply use a <strong>stack<\/strong> to track the index of the previous smaller blocks.<\/p>\n\n\n\n<h2 id=\"algorithm\"><span id=\"algorithm-4\">Algorithm:<\/span><\/h2>\n\n\n\n<ul><li>Declare a stack <strong>S.<\/strong><\/li><li>Traverse the array from left to right:<ul><li>If the current block <strong>A[i]<\/strong> is larger than the top of the stack i.e. <strong>S.top()<\/strong>, it can be inferred that the block at the top of the stack is confined between the current block and the previous block in the stack.<\/li><li>Therefore, perform <strong>S.pop()<\/strong> and add the water that can be stored.<\/li><\/ul><\/li><li>The total volume of water can be calculated as follows:<ul><li>Length = Current index <strong>i<\/strong>&nbsp; &#8211; <strong>S.top() &#8211;<\/strong> <strong>1<\/strong><\/li><li>Width =&nbsp; <strong>min(A[i] &#8211; A[S.top()] &#8211; A[top]<\/strong><\/li><li>Add the total volume to res = <strong>Length X Width<\/strong><\/li><\/ul><\/li><\/ul>\n\n\n\n<h3 id=\"c-code-implementation\"><span id=\"c-code-implementation-4\">C++ Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Solution {\npublic:\n   \n\tint trapping_rain_water(vector&lt;int>&amp; A)\n\t{\n\t\t\/\/Final answer\n\t\tint res = 0;\n\t\tint N = A.size();\n\t\t\n\t\t\/\/Stack to store indices\n\t\tstack&lt;int>S;\n\t\t\n\t\tint i = 0;\n\t\t\n\t\t\/\/Traverse through each block\n\t\twhile(i &lt; N){\n\t\t  \n\t\t  while(!S.empty() and A[i] > A[S.top()]){\n\t\t\t  \n\t\t\t  \/\/Store the height of the top\n\t\t\t  int top = A[S.top()];\n\t\t\t  S.pop();\n\t\t\t  \n\t\t\t  \n\t\t\t  if(S.empty()){\n\t\t\t\t  break;\n\t\t\t  }\n\t\t\t  \n\t\t\t  \/\/Find distance between the left and right height\n\t\t\t  int length = i - S.top() - 1;\n\t\t\t  \/\/Finding width \n\t\t\t  int width = min(A[i], A[S.top()]) - A[top];\n\t\t\t  \n\t\t\t  \/\/Total volume of water added\n\t\t\t  res += length * width;  \t\n\t\t  }\n\t\t  \n\t\t  S.push(i);\n\t\t  i = i + 1;\n\t\t}\n\t\t\n\t\treturn res;\n\t}\n};<\/pre>\n\n\n\n<h3 id=\"-java-code-implementation\"><span id=\"java-code-implementation-3\"><meta charset=\"utf-8\">Java Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public int trapping_rain_water(int[] A) {\n       int N = A.length;\n       int res = 0;\n       Stack&lt;Integer> stack = new Stack&lt;Integer>();\n       int i = 0;\n       while(i &lt; N){\n           while (!stack.isEmpty() &amp;&amp; A[i] > A[stack.peek()]) {\n             \n               int top = A[stack.peek()];\n               stack.pop();\n               if(stack.isEmpty()){\n                   break;\n               }\n               int length =  i - stack.peek() - 1;\n               int width = Math.min(A[i], A[stack.peek()]) - A[top];\n               res += length * width;\n               if (height[leftIndex] &lt;=  height[i]) {\n                   stack.pop();\n               }\n           }\n           stack.push(i);\n           i = i + 1;\n       }\n       return res;\n   }<\/pre>\n\n\n\n<h3 id=\"python-code-implementation\"><span id=\"python-code-implementation-3\">Python Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def trapping_rain_water(A):\n       stack = []\n      \n       res = 0\n       for i in range(len(A)):\n           while stack and A[i] > A[stack[-1]]:\n               pop = stack.pop()\n               if stack:\n                   left = A[stack[-1]]\n                   right = A[i]\n                   res += (min(right, left) - A[pop])*(i-stack[-1]-1)\n                  \n           stack.append(i)\n      \n       return res<\/pre>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(N), since the array is traversed once.<\/li><li><strong>Space Complexity:<\/strong> O(N). Stack takes O(N) space.<\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"two-pointers-approach\">Two Pointers Approach<\/h2>\n\n\n\n<p>In the last approach, though it is solved using a single traversal, it uses an extra space. Can it be improved to O(1) space?<\/p>\n\n\n\n<p>According to <strong>Approach 2<\/strong>, the total volume of water trapped is dependent upon the minimum-maximum of height on the left and right half of the current block. Therefore, instead of considering two arrays to store the heights, we can simply use two variables to store the maximum for the given index. But how?<\/p>\n\n\n\n<p>Take two points, once on the left side of the array and another on the right side. If there is a block on the left, then the total water trapped would be dependent on the direction from right to left and vice versa.<\/p>\n\n\n\n<h2 id=\"algorithm\"><span id=\"algorithm-5\">Algorithm:<\/span><\/h2>\n\n\n\n<ul><li>Initialise two pointers <strong>left = 0 <\/strong>and <strong>right = N &#8211; 1<\/strong> and <strong>res<\/strong> <strong>= 0<\/strong>.<\/li><li>Initialise two variables <strong>left_max = 0 <\/strong>and <strong>right_max = 0<\/strong>, denoting the maximum height on the left and maximum height on the right.<\/li><li>Traverse the array, i.e. <strong>while(left &lt;= right)<\/strong><ul><li>If <strong>A[left] &lt; A[right]<\/strong> and <strong>left_max > A[left]<\/strong><ul><li>Then, add <strong>left_max &#8211;<\/strong> <strong>A[left]<\/strong> to <strong>res<\/strong><\/li><li>Else if <strong>left_max &lt; A[left]<\/strong><ul><li>Update <strong>left_max<\/strong> to <strong>A[left]<\/strong><\/li><\/ul><\/li><li>Increment left pointer<\/li><\/ul><\/li><li>Similarly, if If <strong>A[left] > A[right]<\/strong> and <strong>right_max > A[right]<\/strong><ul><li>Then, add <strong>right_max &#8211;<\/strong> <strong>A[right]<\/strong> to <strong>res<\/strong><\/li><li>Else if <strong>right_max &lt; A[right]<\/strong><ul><li>Update <strong>right_max<\/strong> to <strong>A[right]<\/strong><\/li><\/ul><\/li><li>Increment right pointer<\/li><\/ul><\/li><\/ul><\/li><li>Print <strong>res<\/strong><\/li><\/ul>\n\n\n\n<h3 id=\"c-code-implementation\">C++ Code Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Solution {\npublic:\n   \n\tint trapping_rain_water(vector&lt;int>&amp; A)\n\t{\n\t\tint res = 0;\n\t\tint N = A.size();\n\t\t\n\t\tint left = 0, right = N - 1;\n\t\tint left_max = 0, right_max = 0;\n\t\twhile(left &lt;= right){\n\t\t\tif(A[left] &lt; A[right]){\n\t\t\t\tif(A[left] > left_max){\n\t\t\t\t\tleft_max = A[left];\n\t\t\t\t}\n\t\t\t\telse{\n\t\t\t\t\tres += left_max - A[left];\n\t\t\t\t}\n\t\t\t\tleft = left + 1;\n\t\t\t}\n\t\t\telse{\n\t\t\t\t\tif(A[right] > right_max){\n\t\t\t\t\t\tright_max = A[right];\n\t\t\t\t\t}\n\t\t\t\t\telse{\n\t\t\t\t\t\tres += right_max - A[right];\n\t\t\t\t\t}\n\t\t\t\t\tright = right + 1;\n\t\t\t}\n\t\t}\n\t\treturn res;\n\t}\n};<\/pre>\n\n\n\n<h3 id=\"-java-code-implementation\"><span id=\"java-code-implementation-4\"><meta charset=\"utf-8\">Java Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public int trapping_rain_water(int[] A) {\n           int res =0;\n           int left_max = 0;\n           int right_max = 0;\n           int i = 0;\n           int j = A.length -1;\n           while(i&lt; j){\n               left_max = Math.max(left_max, A[i]);\n               right_max = Math.max(right_max, A[j]);\n               if(left_max &lt; right_max){\n                   res += left_max-A[i];\n                   i++;\n               }\n               else{\n                   res += right_max - A[j];\n                   j--;\n               }\n           }\n           return res;\n       }<\/pre>\n\n\n\n<h3 id=\"-python-code-implementation\"><span id=\"python-code-implementation-4\"><meta charset=\"utf-8\">Python Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def trapping_rain_water(A):\n      \n       i, j = 0, len(A) - 1\n       lMax, rMax = A[i], A[j]\n       res = 0\n       while i &lt; j:\n           left_max = max(left_max, A[i])\n           right_max = max(right_max, A[j])\n           if left_max &lt; right_max:\n               res += left_max - A[i]\n               i += 1\n           else:\n               res += right_max - A[j]\n               j -= 1\n       return res<\/pre>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(N), since the array is traversed once.<\/li><li><strong>Space Complexity:<\/strong> O(1).<\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-problem\">Practice Problem<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/container-with-most-water\/\" target=\"_blank\">Container With Most Water<\/a><\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"frequently-asked-questions\">Frequently Asked Questions<\/h2>\n\n\n\n<h3 id=\"q1-how-many-methods-are-there-to-solve-the-trapping-rainwater-problem\"><span id=\"q-1-how-many-methods-are-there-to-solve-the-trapping-rainwater-problem\">Q.1: How many methods are there to solve the trapping rainwater problem?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>There are mainly 4 methods to solve the problem, all are mentioned above.<\/p>\n\n\n\n<h3 id=\"q2-which-is-the-best-approach-with-respect-to-the-time-and-space-complexity\"><span id=\"q-2-which-is-the-best-approach-with-respect-to-the-time-and-space-complexity\">Q.2: Which is the best approach with respect to the time and space complexity?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>The two-pointer approach is the best approach, it has O(N) time complexity and O(1) space complexity.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given an integer array A[] consisting of N non-negative integers representing an elevation map, where the&hellip;\n","protected":false},"author":5,"featured_media":2511,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[399,417,418],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2507"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2507"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2507\/revisions"}],"predecessor-version":[{"id":21917,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2507\/revisions\/21917"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2511"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2507"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2507"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2507"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}