## The Maximum Volume of Trapped Rain Water in 3D

A classic algorithm question in 2D version is typically described as

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.

For example, Given the input

[0,1,0,2,1,0,1,3,2,1,2,1]

the return value would be

6

The algorithm that I used to solve the above 2D problem is

int trapWaterVolume2D(vector<int> A) { int n = A.size(); vector<int> 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 < n; i++){ leftmost[i] = leftMaxSoFar; if (A[i] > 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 >= 0; i--){ rightmost[i] = rightMaxSoFar; if (A[i] > rightMaxSoFar) rightMaxSoFar = A[i]; } // Summation, O(n) int vol = 0; for (int i = 0; i < n; i++){ vol += max(0, min(leftmost[i], rightmost[i]) - A[i]); } return vol; }

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

int trapWaterVolume3D(vector<vector<int> > A);

Sample graph:

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.

For each point on the terrain consider all paths from that point to the border of the terrain. The level of water would be the minimum of the maximum heights of the points of those paths. To find it we need to perform a slightly modified Dijkstra's algorithm, filling the water level matrix starting from the border.

For every point on the border set the water level to the point height For every point not on the border set the water level to infinity Put every point on the border into the set of active points While the set of active points is not empty: Select the active point P with minimum level Remove P from the set of active points For every point Q adjacent to P: Level(Q) = max(Height(Q), min(Level(Q), Level(P))) If Level(Q) was changed: Add Q to the set of active points

**Trapping Rain Water II,** Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after The Maximum Volume of Trapped Rain Water in 3D (5) A classic algorithm question in 2D version is typically described as 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.

user3290797's "slightly modified Dijkstra algorithm" is closer to Prim's algorithm than Dijkstra's. In minimum spanning tree terms, we prepare a graph with one vertex per tile, one vertex for the outside, and edges with weights equal to the maximum height of their two adjoining tiles (the outside has height "minus infinity").

Given a path in this graph to the outside vertex, the maximum weight of an edge in the path is the height that the water has to reach in order to escape along that path. The relevant property of a minimum spanning tree is that, for every pair of vertices, the maximum weight of an edge in the path in the spanning tree is the minimum possible among all paths between those vertices. The minimum spanning tree thus describes the most economical escape paths for water, and the water heights can be extracted in linear time with one traversal.

As a bonus, since the graph is planar, there's a linear-time algorithm for computing the minimum spanning tree, consisting of alternating Boruvka passes and simplifications. This improves on the O(n log n) running time of Prim.

**The Maximum Volume of Trapped Rain Water in 3D,** This is a lint code question: http://www.lintcode.com/en/problem/trapping-rain-water-ii/ The best solution seems to be using a variant of modified Maximum water that can be accumulated is 6; Complexity Analysis: Time Complexity: O(n). Only one traversal of the array is needed, So time Complexity is O(n). Space Complexity: O(n). Two extra array is needed each of size n.

**Trapping Rain Water,** C++ program to find maximum amount of water that can. // be trapped within given set of bars. #include <bits/stdc++.h>. using namespace std;. int findWater( int In this article, we are going to solve the trapping water problem. This kind of problems are asked very frequently in interviews and online programming challenges. Problem Statement. We need to find the maximum volume of water that can be stored in between buildings or bars as shown in the below image. Assume that width of each bar is 1.

In order to accomplish tapping water problem in 3D i.e., to calculate the maximum volume of trapped rain water you can do something like this:

#include<bits/stdc++.h> using namespace std; #define MAX 10 int new2d[MAX][MAX]; int dp[MAX][MAX],visited[MAX][MAX]; int dx[] = {1,0,-1,0}; int dy[] = {0,-1,0,1}; int boundedBy(int i,int j,int k,int in11,int in22) { if(i<0 || j<0 || i>=in11 || j>=in22) return 0; if(new2d[i][j]>k) return new2d[i][j]; if(visited[i][j]) return INT_MAX; visited[i][j] = 1; int r = INT_MAX; for(int dir = 0 ; dir<4 ; dir++) { int nx = i + dx[dir]; int ny = j + dy[dir]; r = min(r,boundedBy(nx,ny,k,in11,in22)); } return r; } void mark(int i,int j,int k,int in1,int in2) { if(i<0 || j<0 || i>=in1 || j>=in2) return; if(new2d[i][j]>=k) return; if(visited[i][j]) return ; visited[i][j] = 1; for(int dir = 0;dir<4;dir++) { int nx = i + dx[dir]; int ny = j + dy[dir]; mark(nx,ny,k,in1,in2); } dp[i][j] = max(dp[i][j],k); } struct node { int i,j,key; node(int x,int y,int k) { i = x; j = y; key = k; } }; bool compare(node a,node b) { return a.key>b.key; } vector<node> store; int getData(int input1, int input2, int input3[]) { int row=input1; int col=input2; int temp=0; int count=0; for(int i=0;i<row;i++) { for(int j=0;j<col;j++) { if(count==(col*row)) break; new2d[i][j]=input3[count]; count++; } } store.clear(); for(int i = 0;i<input1;i++) { for(int j = 0;j<input2;j++) { store.push_back(node(i,j,new2d[i][j])); } } memset(dp,0,sizeof(dp)); sort(store.begin(),store.end(),compare); for(int i = 0;i<store.size();i++) { memset(visited,0,sizeof(visited)); int aux = boundedBy(store[i].i,store[i].j,store[i].key,input1,input2); if(aux>store[i].key) { memset(visited,0,sizeof(visited)); mark(store[i].i,store[i].j,aux,input1,input2); } } long long result =0 ; for(int i = 0;i<input1;i++) { for(int j = 0;j<input2;j++) { result = result + max(0,dp[i][j]-new2d[i][j]); } } return result; } int main() { cin.sync_with_stdio(false); cout.sync_with_stdio(false); int n,m; cin>>n>>m; int inp3[n*m]; store.clear(); for(int j = 0;j<n*m;j++) { cin>>inp3[j]; } int k = getData(n,m,inp3); cout<<k; return 0; }

**The Maximum Volume of Trapped Rain Water in 3D,** The Maximum Volume of Trapped Rain Water in 3D. Question. A classic algorithm question in 2D version is typically described as. Given n non-negative Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining. Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000. Given the following 3x6 height map: [ [1,4,3,1,3,2], [3,2,1,3,2,4

This problem can be solved using the Priority-Flood algorithm. It's been discovered and published a number of times over the past few decades (and again by other people answering this question), though the specific variant you're looking for is not, to my knowledge, in the literature.

You can find a review paper of the algorithm and its variants here. Since that paper was published an even faster variant has been discovered (link), as well as methods to perform this calculation on datasets of trillions of cells (link). A method for selectively breaching low/narrow divides is discussed here. Contact me if you'd like copies of any of these papers.

I have a repository here with many of the above variants; additional implementations can be found here.

A simple script to calculate volume using the RichDEM library is as follows:

#include "richdem/common/version.hpp" #include "richdem/common/router.hpp" #include "richdem/depressions/Lindsay2016.hpp" #include "richdem/common/Array2D.hpp" /** @brief Calculates the volume of depressions in a DEM @author Richard Barnes (rbarnes@umn.edu) Priority-Flood starts on the edges of the DEM and then works its way inwards using a priority queue to determine the lowest cell which has a path to the edge. The neighbours of this cell are added to the priority queue if they are higher. If they are lower, then they are members of a depression and the elevation of the flooding minus the elevation of the DEM times the cell area is the flooded volume of the cell. The cell is flooded, total volume tracked, and the neighbors are then added to a "depressions" queue which is used to flood depressions. Cells which are higher than a depression being filled are added to the priority queue. In this way, depressions are filled without incurring the expense of the priority queue. @param[in,out] &elevations A grid of cell elevations @pre 1. **elevations** contains the elevations of every cell or a value _NoData_ for cells not part of the DEM. Note that the _NoData_ value is assumed to be a negative number less than any actual data value. @return Returns the total volume of the flooded depressions. @correctness The correctness of this command is determined by inspection. (TODO) */ template <class elev_t> double improved_priority_flood_volume(const Array2D<elev_t> &elevations){ GridCellZ_pq<elev_t> open; std::queue<GridCellZ<elev_t> > pit; uint64_t processed_cells = 0; uint64_t pitc = 0; ProgressBar progress; std::cerr<<"\nPriority-Flood (Improved) Volume"<<std::endl; std::cerr<<"\nC Barnes, R., Lehman, C., Mulla, D., 2014. Priority-flood: An optimal depression-filling and watershed-labeling algorithm for digital elevation models. Computers & Geosciences 62, 117–127. doi:10.1016/j.cageo.2013.04.024"<<std::endl; std::cerr<<"p Setting up boolean flood array matrix..."<<std::endl; //Used to keep track of which cells have already been considered Array2D<int8_t> closed(elevations.width(),elevations.height(),false); std::cerr<<"The priority queue will require approximately " <<(elevations.width()*2+elevations.height()*2)*((long)sizeof(GridCellZ<elev_t>))/1024/1024 <<"MB of RAM." <<std::endl; std::cerr<<"p Adding cells to the priority queue..."<<std::endl; //Add all cells on the edge of the DEM to the priority queue for(int x=0;x<elevations.width();x++){ open.emplace(x,0,elevations(x,0) ); open.emplace(x,elevations.height()-1,elevations(x,elevations.height()-1) ); closed(x,0)=true; closed(x,elevations.height()-1)=true; } for(int y=1;y<elevations.height()-1;y++){ open.emplace(0,y,elevations(0,y) ); open.emplace(elevations.width()-1,y,elevations(elevations.width()-1,y) ); closed(0,y)=true; closed(elevations.width()-1,y)=true; } double volume = 0; std::cerr<<"p Performing the improved Priority-Flood..."<<std::endl; progress.start( elevations.size() ); while(open.size()>0 || pit.size()>0){ GridCellZ<elev_t> c; if(pit.size()>0){ c=pit.front(); pit.pop(); } else { c=open.top(); open.pop(); } processed_cells++; for(int n=1;n<=8;n++){ int nx=c.x+dx[n]; int ny=c.y+dy[n]; if(!elevations.inGrid(nx,ny)) continue; if(closed(nx,ny)) continue; closed(nx,ny)=true; if(elevations(nx,ny)<=c.z){ if(elevations(nx,ny)<c.z){ ++pitc; volume += (c.z-elevations(nx,ny))*std::abs(elevations.getCellArea()); } pit.emplace(nx,ny,c.z); } else open.emplace(nx,ny,elevations(nx,ny)); } progress.update(processed_cells); } std::cerr<<"t Succeeded in "<<std::fixed<<std::setprecision(1)<<progress.stop()<<" s"<<std::endl; std::cerr<<"m Cells processed = "<<processed_cells<<std::endl; std::cerr<<"m Cells in pits = " <<pitc <<std::endl; return volume; } template<class T> int PerformAlgorithm(std::string analysis, Array2D<T> elevations){ elevations.loadData(); std::cout<<"Volume: "<<improved_priority_flood_volume(elevations)<<std::endl; return 0; } int main(int argc, char **argv){ std::string analysis = PrintRichdemHeader(argc,argv); if(argc!=2){ std::cerr<<argv[0]<<" <Input>"<<std::endl; return -1; } return PerformAlgorithm(argv[1],analysis); }

It should be straight-forward to adapt this to whatever 2d array format you are using

In pseudocode, the following is equivalent to the foregoing:

Let PQ be a priority-queue which always pops the cell of lowest elevation Let Closed be a boolean array initially set to False Let Volume = 0 Add all the border cells to PQ. For each border cell, set the cell's entry in Closed to True. While PQ is not empty: Select the top cell from PQ, call it C. Pop the top cell from PQ. For each neighbor N of C: If Closed(N): Continue If Elevation(N)<Elevation(C): Volume += (Elevation(C)-Elevation(N))*Area Add N to PQ, but with Elevation(C) Else: Add N to PQ with Elevation(N) Set Closed(N)=True

**The Fake Geek's blog: Trapping Rain Water II,** After the rain, water are trapped between the blocks. The total volume of water trapped is 4. When it turns to 3D , it becomes a little bit more difficult. We know that the highest amount of water the container can hold depends on 3: Then, for each tower, the amount of water on it is min(ltr, rtl) - towerHeight, where ltr is the value for that tower in the left-to-right monotonic sweep we did before, i.e. the maximum height of any tower to the left of us (including ourselves 1), and rtl is the same for the right-to-left sweep.

**Trapping Rain Water,** You wrote very clear and readable code: the variable names express the purpose; you use const and let instead of the old var; you You are given an input array whose each element represents the height of a line towers. The width of every tower is 1. It starts raining. How much water is collected between the towers? Example. Input: [1,5,3,7,2] , Output: 2 units Explanation: 2 units of water collected between towers of height 5 and 7 * * *w* *w* *** **** *****

**Rain Water Trapped,** Rain Water Trapped: 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 Volume of rainfall. From amount of rain and area. Other subcategories index. Other calcs index. The catchment area is multiplied by the depth of rain that falls on it to give the total volume of water produced. Factors such as evaporation, wetting, and soaking into the ground are not considered here.

**Google Interview Problem: Trapping Rain Water Part 1,** This is part 1 of the "Trapping Rain Water" problem. Making these videos needs a Duration: 9:18
Posted: Jul 29, 2018 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. The above elevation map 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. Thanks Marcos for contributing this image!