title: The Maximum Volume of Trapped Rain Water in 3D
body: <p>A classic algorithm question in 2D version is typically described as </p>
  
  <p>Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. </p>
  
  <p>For example, Given the input </p>
  
  <pre><code>[0,1,0,2,1,0,1,3,2,1,2,1] 
  </code></pre>
  
  <p>the return value would be </p>
  
  <pre><code>6
  </code></pre>
  
  <p><img src="https://i.stack.imgur.com/4oFm2.png" alt="enter image description here"></p>
  
  <p>The algorithm that I used to solve the above 2D problem is </p>
  
  <pre><code>int trapWaterVolume2D(vector&lt;int&gt; A) {
      int n = A.size();
      vector&lt;int&gt; leftmost(n, 0), rightmost(n, 0);
  
      //left exclusive scan, O(n), the highest bar to the left each point
      int leftMaxSoFar = 0;
      for (int i = 0; i &lt; n; i++){
          leftmost[i] = leftMaxSoFar;
          if (A[i] &gt; leftMaxSoFar) leftMaxSoFar = A[i];
      }
  
  
      //right exclusive scan, O(n), the highest bar to the right each point
      int rightMaxSoFar = 0;
      for (int i = n - 1; i &gt;= 0; i--){
          rightmost[i] = rightMaxSoFar;
          if (A[i] &gt; rightMaxSoFar) rightMaxSoFar = A[i];
      }
  
      // Summation, O(n)
      int vol = 0;
      for (int i = 0; i &lt; n; i++){
          vol += max(0, min(leftmost[i], rightmost[i]) - A[i]);
      }
      return vol;
  }
  </code></pre>
  
  <p>My Question is how to make the above algorithm extensible to the 3D version of the problem, to compute the maximum of water trapped in real-world 3D terrain. i.e. To implement </p>
  
  <pre><code>int trapWaterVolume3D(vector&lt;vector&lt;int&gt; &gt; A);
  </code></pre>
  
  <p>Sample graph:</p>
  
  <p><img src="https://i.stack.imgur.com/hjwPc.png" alt="enter image description here"></p>
  
  <p>We know the elevation at each (x, y) point and the goal is to compute the maximum volume of water that can be trapped in the shape. Any thoughts and references are welcome.</p>