Problem: 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.
Example:
Given the following 3x6 height map:
[
[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1]
]
Return 4.
The above image represents the elevation map [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] before the rain.
After the rain, water is trapped between the blocks. The total volume of water trapped is 4.
Approach: To understand the approach, let's take an example:
[
[12,13,1,12],
[13,4,13,12],
[13,8,10,12],
[12,13,12,12],
[13,13,13,13]
]
1. Let's take a cell (1,1) with height = 4. It's neighbors heights are 13, 13, 8, 13 (top, right, bottom, left). The minimum height among all the neighbors are 8 so if it was just these cells the cell (1, 1) could hold (8 - 4 =) 4 units of water but now if you see the neighbor cell with minimum height(8) is (2, 1). This cell is surrounded by the cells with heights 4, 10, 13, 13. We don't care about 4 as it is less than 8 so the minimum height among all other cells is 10 so if you visualize this matrix as 2D elevation map, you will realize that cell (2, 1) can hold 10 - 8 = 2 units of water which is obvious but the amount of water at (1, 1) will also change and it will become 10 - 4 = 6 units of water.
Now we again have to look at what is the minimum length of neighbors of cell with height 10 which is (2, 2). The heights are 13, 12, 12, 8. The minimum height is 12 (8 is not considered as it is less than 10) so we can say cell (2, 2) can hold 12 - 10 = 2 units of water but if you see the amount of water at cells (2, 1), (1, 1) will also be changed and it will become 12 - 8 = 4 units and 12 - 4 =8 units respectively.
2. All the boundaries cell can't hold water as they are open from at least one side.
If you read point 1, you will see that we are picking the next minimum cell and calculating the amount of water so we can use Priority Queue here with height as comparer.
Basically we do kind of BFS where we use priority queue instead of a normal queue.
That's all!
Implementation in C#:
public class HeightComparer : IComparer<int[]>
{
public int Compare([AllowNull] int[] x, [AllowNull] int[] y)
{
return x[2].CompareTo(y[2]);
}
}
public int TrapRainWater(int[][] heightMap)
{
int rows = heightMap?.Length ?? 0;
if (rows <= 1)
{
return 0;
}
int cols = heightMap[0].Length;
if (cols <= 1)
{
return 0;
}
bool[,] visited = new bool[rows, cols];
PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(rows * cols, new HeightComparer());
// Add all the boundary cells, no need to update amount of water
// as boundary cells are open
for (int i = 0; i < rows; ++i)
{
priorityQueue.Push(new int[] { i, 0, heightMap[i][0] });
priorityQueue.Push(new int[] { i, cols - 1, heightMap[i][cols - 1] });
visited[i, 0] = true;
visited[i, cols - 1] = true;
}
for (int i = 0; i < cols; ++i)
{
priorityQueue.Push(new int[] { 0, i, heightMap[0][i] });
priorityQueue.Push(new int[] { rows - 1, i, heightMap[rows - 1][i] });
visited[0, i] = true;
visited[rows - 1, i] = true;
}
int currMax = 0, amountOfWater = 0;
while (priorityQueue.Count > 0)
{
int[] currCell = priorityQueue.Top;
priorityQueue.Pop();
currMax = Math.Max(currMax, currCell[2]);
this.AddNeighborsToPQAndUpdateWater(heightMap, priorityQueue, currCell[0], currCell[1], currMax, visited, ref amountOfWater);
}
return amountOfWater;
}
private void AddNeighborsToPQAndUpdateWater(
int[][] heightMap,
PriorityQueue<int[]> priorityQueue,
int row,
int col,
int currMax,
bool[,] visited,
ref int amountOfWater)
{
// Up neighbor
if (this.IsValidAndUnvisitedCell(heightMap, row - 1, col, visited))
{
if (currMax > heightMap[row - 1][col])
{
amountOfWater += currMax - heightMap[row - 1][col];
}
priorityQueue.Push(new int[] { row - 1, col, heightMap[row - 1][col] });
visited[row - 1, col] = true;
}
// Down neighbor
if (this.IsValidAndUnvisitedCell(heightMap, row + 1, col, visited))
{
if (currMax > heightMap[row + 1][col])
{
amountOfWater += currMax - heightMap[row + 1][col];
}
priorityQueue.Push(new int[] { row + 1, col, heightMap[row + 1][col] });
visited[row + 1, col] = true;
}
// Left Neighbor
if (this.IsValidAndUnvisitedCell(heightMap, row, col - 1, visited))
{
if (currMax > heightMap[row][col - 1])
{
amountOfWater += currMax - heightMap[row][col - 1];
}
priorityQueue.Push(new int[] { row, col - 1, heightMap[row][col - 1] });
visited[row, col - 1] = true;
}
// Right neighbor
if (this.IsValidAndUnvisitedCell(heightMap, row, col + 1, visited))
{
if (currMax > heightMap[row][col + 1])
{
amountOfWater += currMax - heightMap[row][col + 1];
}
priorityQueue.Push(new int[] { row, col + 1, heightMap[row][col + 1] });
visited[row, col + 1] = true;
}
}
private bool IsValidAndUnvisitedCell(int[][] heightMap, int row, int col, bool[,] visited)
{
if (row < 0 || row >= heightMap.Length || col < 0 || col >= heightMap[0].Length || visited[row, col])
{
return false;
}
return true;
}
Complexity: O(m*n*log(m*n)) where m is number of rows and n is number of cols
