{"id":867,"date":"2025-08-11T12:09:04","date_gmt":"2025-08-11T06:39:04","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=867"},"modified":"2025-08-11T12:09:05","modified_gmt":"2025-08-11T06:39:05","slug":"trapping-rain-water","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/","title":{"rendered":"Trapping Rain Water | Leetcode 42 | Brute, Better and Optimal Solution using Stack"},"content":{"rendered":"\n<p>Given&nbsp;<code>n<\/code>&nbsp;non-negative integers representing an elevation map where the width of each bar is&nbsp;<code>1<\/code>, compute how much water it can trap after raining.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/trapping-rain-water\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2018\/10\/22\/rainwatertrap.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> height = [0,1,0,2,1,0,1,3,2,1,2,1]<br><strong>Output:<\/strong> 6<br><strong>Explanation:<\/strong> The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> height = [4,2,0,3,2,5]<br><strong>Output:<\/strong> 9<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>n == height.length<\/code><\/li>\n\n\n\n<li><code>1 &lt;= n &lt;= 2 * 10<sup>4<\/sup><\/code><\/li>\n\n\n\n<li><code>0 &lt;= height[i] &lt;= 10<sup>5<\/sup><\/code><\/li>\n<\/ul>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-36452545-7a29-4f43-a482-41476709d797\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#0-brute-solution-prefix-and-suffix-arrays\" style=\"\">Brute Solution: Prefix and Suffix Arrays<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#1-intuition-and-approach\" style=\"\">Intuition and Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#2-code-implementation\" style=\"\">Code Implementation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#3-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#4-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#5-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#6-better-solution-one-suffix-array-running-left-max\" style=\"\">Better Solution: One Suffix Array + Running Left Max<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#7-intuition-and-approach\" style=\"\">Intuition and Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#8-code-implementation\" style=\"\">Code Implementation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#9-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#10-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#11-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#12-optimal-solution-two-pointer-technique\" style=\"\">Optimal Solution: Two-Pointer Technique<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#13-intuition-and-approach\" style=\"\">Intuition and Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#14-code-implementation\" style=\"\">Code Implementation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#15-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#16-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#17-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/#18-final-takeaways\" style=\"\">Final Takeaways<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-brute-solution-prefix-and-suffix-arrays\">Brute Solution: Prefix and Suffix Arrays<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition-and-approach\">Intuition and Approach<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>For each position i, find:\n<ul class=\"wp-block-list\">\n<li>The tallest bar on the left up to i (call it prefixMax[i]).<\/li>\n\n\n\n<li>The tallest bar on the right from i to the end (call it suffixMax[i]).<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Water at position i is limited by the shorter side among these two maxima.<\/li>\n\n\n\n<li>So, water at i = min(prefixMax[i], suffixMax[i]) \u2212 height[i].<\/li>\n\n\n\n<li>Add this for all positions to get the total trapped water.<\/li>\n<\/ul>\n\n\n\n<p>Why it works:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Water can only stand up to the height of the shorter wall among left and right sides.<\/li>\n\n\n\n<li>Precomputing both sides for every index makes calculation straightforward.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-code-implementation\">Code Implementation<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def trap(self, height: List[int]) -&gt; int:\n        if not height or len(height) &lt; 3:\n            return 0\n\n        n = len(height)\n\n        # Initialize prefixMax and suffixMax arrays.\n        prefixMax = [0] * n\n        suffixMax =  * n\n\n        # Fill the prefixMax array (tallest from the left up to i).\n        prefixMax = height\n        for i in range(1, n):\n            prefixMax[i] = max(prefixMax[i - 1], height[i])\n\n        # Fill the suffixMax array (tallest from the right from i to end).\n        suffixMax[n - 1] = height[n - 1]\n        for i in range(n - 2, -1, -1):\n            suffixMax[i] = max(suffixMax[i + 1], height[i])\n\n        # Calculate the total water trapped.\n        trapped_water = 0\n        for i in range(n):\n            # Water at i is the difference between the limiting wall and bar height.\n            trapped_water += min(prefixMax[i], suffixMax[i]) - height[i]\n\n        return trapped_water\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">trap<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">height<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> height <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(height) &lt; <\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(height)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Initialize prefixMax and suffixMax arrays.<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        prefixMax = [<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] * n<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        suffixMax =  * n<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Fill the prefixMax array (tallest from the left up to i).<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        prefixMax = height<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            prefixMax[i] = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(prefixMax[i - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">], height[i])<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Fill the suffixMax array (tallest from the right from i to end).<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        suffixMax[n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] = height[n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n - <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">, -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            suffixMax[i] = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(suffixMax[i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">], height[i])<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Calculate the total water trapped.<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        trapped_water = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Water at i is the difference between the limiting wall and bar height.<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            trapped_water += <\/span><span style=\"color: #DCDCAA\">min<\/span><span style=\"color: #D4D4D4\">(prefixMax[i], suffixMax[i]) - height[i]<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> trapped_water<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code-explanation\">Code Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We first compute the tallest bar to the left for each index (prefixMax).<\/li>\n\n\n\n<li>Then we compute the tallest bar to the right for each index (suffixMax).<\/li>\n\n\n\n<li>For each index, the water is the smaller of these two heights minus the actual bar height.<\/li>\n\n\n\n<li>Summing across all indices gives total trapped water.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Precise: Time O(n + n + n) = O(3n), Space O(2n).<\/li>\n\n\n\n<li>Simplified: Time O(n), Space O(n).<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-conclusion\">Conclusion<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Very easy to understand and implement.<\/li>\n\n\n\n<li>Uses extra memory for two arrays, but logic is simple and reliable.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"6-better-solution-one-suffix-array-running-left-max\">Better Solution: One Suffix Array + Running Left Max<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"7-intuition-and-approach\">Intuition and Approach<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We can avoid storing both arrays.<\/li>\n\n\n\n<li>Precompute only right-side maxima in an array (rightMax).<\/li>\n\n\n\n<li>As we scan from left to right, keep a running leftMax.<\/li>\n\n\n\n<li>Water at i = min(leftMax, rightMax[i]) \u2212 height[i].<\/li>\n<\/ul>\n\n\n\n<p>Why it works:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>You still need both left and right maxima for each position.<\/li>\n\n\n\n<li>The left maximum can be kept as a single number updated as we move forward.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"8-code-implementation\">Code Implementation<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"from typing import List\n\nclass Solution:\n    def trap(self, height: List[int]) -&gt; int:\n        n = len(height)\n        if n &lt; 3:\n            return 0\n\n        # rightMax[i] = max(height[i..n-1])\n        rightMax = [0] * n\n        rightMax[-1] = height[-1]\n        for i in range(n - 2, -1, -1):\n            rightMax[i] = max(rightMax[i + 1], height[i])\n\n        trapped = 0\n        leftMax = 0\n        for i in range(n):\n            # Update leftMax up to current i\n            leftMax = max(leftMax, height[i])\n            # Water at i is limited by the lower of leftMax and rightMax[i]\n            trapped += min(leftMax, rightMax[i]) - height[i]\n\n        return trapped\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #C586C0\">from<\/span><span style=\"color: #D4D4D4\"> typing <\/span><span style=\"color: #C586C0\">import<\/span><span style=\"color: #D4D4D4\"> List<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">trap<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">height<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(height)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> n &lt; <\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># rightMax[i] = max(height[i..n-1])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        rightMax = [<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] * n<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        rightMax[-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] = height[-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n - <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">, -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            rightMax[i] = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(rightMax[i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">], height[i])<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        trapped = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        leftMax = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Update leftMax up to current i<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            leftMax = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(leftMax, height[i])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Water at i is limited by the lower of leftMax and rightMax[i]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            trapped += <\/span><span style=\"color: #DCDCAA\">min<\/span><span style=\"color: #D4D4D4\">(leftMax, rightMax[i]) - height[i]<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> trapped<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-code-explanation\">Code Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We compute rightMax once by scanning from right to left.<\/li>\n\n\n\n<li>We maintain leftMax on the fly while scanning from left to right.<\/li>\n\n\n\n<li>At each index, the smaller of leftMax and rightMax[i] determines the water level.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Precise: Time O(n + n) = O(2n), Space O(n).<\/li>\n\n\n\n<li>Simplified: Time O(n), Space O(n).<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-conclusion\">Conclusion<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Same core idea as Brute, but saves memory by avoiding the full left array.<\/li>\n\n\n\n<li>A nice balance between simplicity and space saving.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"12-optimal-solution-two-pointer-technique\">Optimal Solution: Two-Pointer Technique<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-intuition-and-approach\">Intuition and Approach<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The side with the smaller current height limits the water.<\/li>\n\n\n\n<li>Use two pointers:\n<ul class=\"wp-block-list\">\n<li>left at the start, right at the end.<\/li>\n\n\n\n<li>leftMax stores the tallest seen so far from the left.<\/li>\n\n\n\n<li>rightMax stores the tallest seen so far from the right.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Move the pointer on the smaller side inward:\n<ul class=\"wp-block-list\">\n<li>If height[left] &lt; height[right]:\n<ul class=\"wp-block-list\">\n<li>If height[left] &lt; leftMax, water += leftMax \u2212 height[left].<\/li>\n\n\n\n<li>Else update leftMax.<\/li>\n\n\n\n<li>Move left forward.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Else do the symmetric steps on the right.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<p>Why it works:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The water at the smaller side depends only on that side\u2019s max, not on the far side.<\/li>\n\n\n\n<li>This lets us decide locally which pointer to move and how much water to add, in one pass.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"14-code-implementation\">Code Implementation<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def trap(self, height: List[int]) -&gt; int:\n        # Edge case: If the height list is empty or has less than 3 elements, no water can be trapped.\n        if not height or len(height) &lt; 3:\n            return 0\n\n        # Initialize two pointers and variables to keep track of maximum heights.\n        left, right = 0, len(height) - 1\n        leftMax, rightMax = 0, 0\n        trapped_water = 0\n\n        # Traverse the elevation map using two pointers.\n        while left &lt; right:\n            # Compare the heights at both pointers.\n            if height[left] &lt; height[right]:\n                # Calculate water trapped at the left index.\n                if height[left] &gt;= leftMax:\n                    leftMax = height[left]  # Update leftMax.\n                else:\n                    trapped_water += leftMax - height[left]  # Water trapped.\n                left += 1  # Move left pointer to the right.\n            else:\n                # Calculate water trapped at the right index.\n                if height[right] &gt;= rightMax:\n                    rightMax = height[right]  # Update rightMax.\n                else:\n                    trapped_water += rightMax - height[right]  # Water trapped.\n                right -= 1  # Move right pointer to the left.\n\n        return trapped_water\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">trap<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">height<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Edge case: If the height list is empty or has less than 3 elements, no water can be trapped.<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> height <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(height) &lt; <\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Initialize two pointers and variables to keep track of maximum heights.<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        left, right = <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(height) - <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        leftMax, rightMax = <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        trapped_water = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Traverse the elevation map using two pointers.<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> left &lt; right:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Compare the heights at both pointers.<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> height[left] &lt; height[right]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># Calculate water trapped at the left index.<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> height[left] &gt;= leftMax:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    leftMax = height[left]  <\/span><span style=\"color: #6A9955\"># Update leftMax.<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    trapped_water += leftMax - height[left]  <\/span><span style=\"color: #6A9955\"># Water trapped.<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                left += <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Move left pointer to the right.<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># Calculate water trapped at the right index.<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> height[right] &gt;= rightMax:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    rightMax = height[right]  <\/span><span style=\"color: #6A9955\"># Update rightMax.<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    trapped_water += rightMax - height[right]  <\/span><span style=\"color: #6A9955\"># Water trapped.<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                right -= <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Move right pointer to the left.<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> trapped_water<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"15-code-explanation\">Code Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We always process the side that is shorter because that side limits the water level there.<\/li>\n\n\n\n<li>If the current bar on that side is lower than the recorded max for that side, the difference is the water trapped on top of that bar.<\/li>\n\n\n\n<li>This avoids building any extra arrays and finishes in one pass.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"16-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Precise: Time O(n), Space O(1).<\/li>\n\n\n\n<li>Simplified: Fastest and most memory-efficient.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"17-conclusion\">Conclusion<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Best approach for interviews and production use.<\/li>\n\n\n\n<li>Minimal memory, single scan, clean logic once you know the insight.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"18-final-takeaways\">Final Takeaways<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Water at a position depends on the shorter of the tallest bars to its left and right.<\/li>\n\n\n\n<li><strong>Brute<\/strong>: Two arrays (easiest to grasp).<\/li>\n\n\n\n<li><strong>Better<\/strong>: One array + running left max (saves memory).<\/li>\n\n\n\n<li><strong>Optimal<\/strong>: Two pointers (fastest and least memory).<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given&nbsp;n&nbsp;non-negative integers representing an elevation map where the width of each bar is&nbsp;1, compute how much water it can trap after raining. Here&#8217;s the [Problem Link] to begin with. Example 1: Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]Output: 6Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water<\/p>\n","protected":false},"author":1,"featured_media":869,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ub_ctt_via":"","footnotes":""},"categories":[3,5],"tags":[18,37],"class_list":{"0":"post-867","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-expert","9":"tag-hard","10":"tag-stack-and-queues"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/08\/trapping-rain-water-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/867","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=867"}],"version-history":[{"count":2,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/867\/revisions"}],"predecessor-version":[{"id":874,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/867\/revisions\/874"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/869"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=867"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=867"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=867"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}