Problem Statement
The task revolves around calculating the volume of water trapped on a 2D topographic map after rainfall. Specifically, we are given a matrix named heightMap where each element represents the elevation of a square unit cell of the terrain. The goal is to calculate the total volume of water that remains trapped between the elevated regions of the map post-rain. The matrix dimensions, m x n, depict the size of the elevation map. This computational challenge involves dealing with spatial structures on a grid and determining the interaction between them when subjected to water accumulation scenarios.
Examples
Example 1
Input:
heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output:
4
Explanation:
After the rain, water is trapped between the blocks. We have two small ponds 1 and 3 units trapped. The total volume of water trapped is 4.
Example 2
Input:
heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
Output:
10
Constraints
m == heightMap.lengthn == heightMap[i].length1 <= m, n <= 2000 <= heightMap[i][j] <= 2 * 104
Approach and Intuition
Understanding the water trapping on a 2D map can be visualized similar to a 3D landscape where rain falls uniformly over the area. Post-rain, some areas of the map, depending on their surrounding elevation, will collect and hold water. Here's how we can intuit the process:
- Identify low points in the map where water is likely to collect. These points will typically be surrounded by higher points on all sides.
- Expand outward from these initial low points, checking neighbors to determine if they can also hold water without spilling over to a lower height.
- As we inspect each cell, calculate the water volume it can hold by comparing its height with its immediate surroundings. The difference in height, if surrounded by higher cells, determines the depth of the trapped water in that cell.
- Accumulate the volume for all cells that trap water.
Example Interpretations based on the examples provided:
- For example 1 from the input
[[1,4,3,1,3,2], [3,2,1,3,2,4], [2,3,3,2,3,1]], visualize a small basin where there are pockets (depicted by lower numbers surrounded by higher numbers). After simulating rain, these pockets trap water. The volume, in this case, was calculated as4units. - In a more substantial case like example 2 with a deeper center at level
1and surrounded by walls of3s, the water trapped is greater. The calculation provided the trapped volume as10units, showcasing a more extensive central pool.
- For example 1 from the input
These examples adhere strictly to the constraints that the matrix is at least
1x1and at most200x200with the heights of each cell ranging from0to20000, ensuring that computations remain manageable yet potentially detailed and complex depending on the landscape given.
Solutions
- C++
- Java
- Python
class Solution {
public:
int calculateWaterTrapping(vector<vector<int>>& elevationMap) {
// Direction vectors
int deltaRow[4] = {0, 0, -1, 1};
int deltaCol[4] = {-1, 1, 0, 0};
int rows = elevationMap.size();
int cols = elevationMap[0].size();
vector<vector<bool>> seen(rows, vector<bool>(cols, false));
// Min-heap to store the boundary cells
priority_queue<WaterCell> edges;
// Process the boundary by adding the first and last column of each row
for (int r = 0; r < rows; r++) {
edges.push(WaterCell(elevationMap[r][0], r, 0));
edges.push(WaterCell(elevationMap[r][cols - 1], r, cols - 1));
seen[r][0] = seen[r][cols - 1] = true;
}
// Process the boundary by adding the first and last row
for (int c = 0; c < cols; c++) {
edges.push(WaterCell(elevationMap[0][c], 0, c));
edges.push(WaterCell(elevationMap[rows - 1][c], rows - 1, c));
seen[0][c] = seen[rows - 1][c] = true;
}
int trappedWater = 0;
while (!edges.empty()) {
WaterCell cell = edges.top();
edges.pop();
int currentR = cell.row;
int currentC = cell.col;
int boundaryHeight = cell.height;
for (int d = 0; d < 4; d++) {
int nr = currentR + deltaRow[d];
int nc = currentC + deltaCol[d];
if (isWithinBounds(nr, nc, rows, cols) && !seen[nr][nc]) {
int neighborHeight = elevationMap[nr][nc];
if (neighborHeight < boundaryHeight) {
trappedWater += boundaryHeight - neighborHeight;
}
edges.push(WaterCell(max(neighborHeight, boundaryHeight), nr, nc));
seen[nr][nc] = true;
}
}
}
return trappedWater;
}
private:
class WaterCell {
public:
int height;
int row;
int col;
WaterCell(int h, int r, int c) : height(h), row(r), col(c) {}
bool operator<(const WaterCell& other) const {
return height > other.height; // Min-heap by reversing comparison
}
};
bool isWithinBounds(int row, int col, int maxRows, int maxCols) {
return row >= 0 && col >= 0 && row < maxRows && col < maxCols;
}
};
This solution addresses the problem of computing the volume of water that can be trapped in a 3D landscape represented by a 2D elevation map. The algorithm employs a priority queue (min-heap) to dynamically select the lowest boundary on the surface, and a breadth-first search strategy to visit and calculate trapped water for each cell. The solution is implemented in C++ and outlined below:
- The problem is initiated by creating a priority queue to keep track of all cells on the perimeter of the elevation map, which are considered as initial boundaries. Cells are represented by an inner class
WaterCell, which stores a cell's height along with its row and column index. - Every boundary cell is marked as seen or visited to prevent re-examination, using a 2D vector of boolean values.
- From each current boundary cell, adjacent cells are examined in four cardinal directions (North, South, East, West). This process is facilitated by two arrays denoting row and column shifts.
- For each adjacent cell, the algorithm checks if it’s within bounds and not yet visited. If the neighbor cell’s elevation is lower than the current boundary cell's elevation, the difference in elevation is treated as the volume of trapped water. The neighbor then becomes part of the boundary, and its height is adjusted to the greater value between its own height and the current boundary height; this ensures that future calculations respect the water surface created by earlier trappings.
- The process repeats until all cells in the elevation map are either visited or considered as water trapping boundaries.
- The accumulated trapped water is returned as the result.
This approach not only systematically expands the boundary inward but also ensures that the lowest edges are processed first, thus maximizing the trapped water calculation by making optimal local decisions that lead to the global optimum.
class WaterTrapSolver {
public int calculateWater(int[][] elevationMap) {
int[] rowDir = { -1, 1, 0, 0 };
int[] colDir = { 0, 0, -1, 1 };
int numRows = elevationMap.length;
int numCols = elevationMap[0].length;
boolean[][] visitedAreas = new boolean[numRows][numCols];
PriorityQueue<GridCell> boundaryQueue = new PriorityQueue<>();
for (int row = 0; row < numRows; row++) {
boundaryQueue.offer(new GridCell(elevationMap[row][0], row, 0));
boundaryQueue.offer(new GridCell(elevationMap[row][numCols - 1], row, numCols - 1));
visitedAreas[row][0] = true;
visitedAreas[row][numCols - 1] = true;
}
for (int col = 0; col < numCols; col++) {
boundaryQueue.offer(new GridCell(elevationMap[0][col], 0, col));
boundaryQueue.offer(new GridCell(elevationMap[numRows - 1][col], numRows - 1, col));
visitedAreas[0][col] = true;
visitedAreas[numRows - 1][col] = true;
}
int trappedWater = 0;
while (!boundaryQueue.isEmpty()) {
GridCell cell = boundaryQueue.poll();
int row = cell.row;
int col = cell.col;
int boundaryHeight = cell.height;
for (int d = 0; d < 4; d++) {
int newRow = row + rowDir[d];
int newCol = col + colDir[d];
if (isInBounds(newRow, newCol, numRows, numCols) && !visitedAreas[newRow][newCol]) {
int newHeight = elevationMap[newRow][newCol];
if (newHeight < boundaryHeight) {
trappedWater += boundaryHeight - newHeight;
}
boundaryQueue.offer(new GridCell(Math.max(newHeight, boundaryHeight), newRow, newCol));
visitedAreas[newRow][newCol] = true;
}
}
}
return trappedWater;
}
private static class GridCell implements Comparable<GridCell> {
int height;
int row;
int col;
public GridCell(int height, int row, int col) {
this.height = height;
this.row = row;
this.col = col;
}
@Override
public int compareTo(GridCell other) {
return Integer.compare(this.height, other.height);
}
}
private boolean isInBounds(int row, int col, int numRows, int numCols) {
return row >= 0 && col >= 0 && row < numRows && col < numCols;
}
}
The provided Java solution for the "Trapping Rain Water II" problem calculates the total amount of water trapped in a 2D elevation map. The method employs a breadth-first search-like algorithm utilizing a priority queue to efficiently process grid cells based on their elevation from lowest to highest. This ensures that one always processes the lowest boundary to find potential trapped water.
- The
calculateWatermethod initializes direction arrays to facilitate movement in four directions on the grid (up, down, left, right). - A
PriorityQueue(boundaryQueue) is used to store and sort the boundary cells based on their heights. - The boundaries of the elevation map grid are loaded into the queue first, ensuring that the edges are processed before inner cells.
- The method iteratively processes each cell in the queue, examining its four neighboring cells. If the neighboring cell's elevation is lower than the processed cell's boundary height, the difference in height represents trapped water.
- To simulate water overflowing and filling, the neighbor is then added to the queue with an updated maximum height of its original height or the boundary height, ensuring correct subsequent water trapping calculation.
- A boolean matrix (
visitedAreas) keeps track of cells already processed to avoid redundant calculations.
As each boundary cell is processed, marking it as visited and evaluating its neighbors for potential trapped water volumes efficiently simulate water filling the low-lying areas surrounded by higher elevations, leading to the total volume of trapped water being returned at the end. This method ensures that each cell is processed once, optimizing the solution's efficiency.
class WaterTrap:
class GridCell:
def __init__(self, h, x, y):
self.h = h
self.x = x
self.y = y
def __lt__(self, other):
return self.h < other.h
def _valid(self, x, y, xmax, ymax):
return 0 <= x < xmax and 0 <= y < ymax
def calculateWater(self, heights):
d_x = [0, 0, -1, 1]
d_y = [-1, 1, 0, 0]
max_x = len(heights)
max_y = len(heights[0])
seen = [[False] * max_y for _ in range(max_x)]
edges = []
for i in range(max_x):
heapq.heappush(edges, self.GridCell(heights[i][0], i, 0))
heapq.heappush(edges, self.GridCell(heights[i][max_y - 1], i, max_y - 1))
seen[i][0] = seen[i][max_y - 1] = True
for j in range(max_y):
heapq.heappush(edges, self.GridCell(heights[0][j], 0, j))
heapq.heappush(edges, self.GridCell(heights[max_x - 1][j], max_x - 1, j))
seen[0][j] = seen[max_x - 1][j] = True
water_trapped = 0
while edges:
cell = heapq.heappop(edges)
for d in range(4):
new_x = cell.x + d_x[d]
new_y = cell.y + d_y[d]
if self._valid(new_x, new_y, max_x, max_y) and not seen[new_x][new_y]:
next_h = heights[new_x][new_y]
if next_h < cell.h:
water_trapped += cell.h - next_h
heapq.heappush(edges, self.GridCell(max(next_h, cell.h), new_x, new_y))
seen[new_x][new_y] = True
return water_trapped
Trapping Rain Water II is a problem that calculates the volume of water trapped in a 3D surface represented as a 2D grid using the Python programming language. The solution involves constructing a min-heap to efficiently retrieve the lowest perimeter cell of the grid and using it as a starting point for water trapping calculations.
Here's how the implementation breaks down:
- Define the
GridCellclass to represent a cell with a height and coordinates. Override the less than operator to compare cells based on height which helps in ordering the cells in a priority queue. - Create a helper function
_validto check whether given coordinates are within the grid boundary. - Initialize a
calculateWaterfunction to perform the main computation:- Initialize variables and data structures, including the 2D list
seento keep track of processed cells and the priority queueedgesfor processing cells in order of their heights. - Push all perimeter cells into the heap (
edges) and mark them as seen. - Process cells from the heap. For each cell processed, check its four neighboring cells:
- Use directional arrays
d_xandd_yto find neighboring cells. - If the neighboring cell is valid and unvisited:
- Calculate trapped water if the neighboring cell's height is less than the current cell's height.
- Push the neighboring cell (or an elevated version of it if the neighboring height is lower) into the heap for future processing.
- Mark the neighboring cell as seen.
- Use directional arrays
- Initialize variables and data structures, including the 2D list
This method spreads from the perimeter inwards, ensuring that the shortest bars (grid cells) are processed first, allowing water trapping calculations between taller bars further inside the perimeter. The result is the sum of trapped water in all eligible cell gaps. This greedy algorithm solution is efficient due to the use of the priority queue and careful management of state with the seen list.
No comments yet.