Trapping Rainwater II

[darwinrlo]

We have a grid. Each grid cell may have a block on it. Blocks have a width and height of 1. But their heights may be 0 or greater.

[darwinrlo]

Start with the largest enclosing space, the space that is enclosed by the blocks at the edges of the grid.

We put all the boundary blocks into a heap. Then we extract the shortest one, breaking ties arbitrarily. At this point, we can compute the amount of water collected by neighboring, non-boundary cells. Here's why.

(Do we also compute the water collected by adjacent cells that are part of the boundary?)

[darwinrlo]

Create a heap and let it contain at each point in the execution of the program the blocks of a boundary of one or more enclosed spaces. We start with the boundary of the largest enclosing space: the border of the entire grid.

• Take the shortest block of the boundary. Compute the water collected by adjacent cells. The block itself will not collect any water.

Start with the greatest enclosing space. Then compute the water collected for cells that are adjacent to the current boundary.

[darwinrlo]

The min-heap contains the blocks of the boundary of an enclosed space. At each point in time, it contains the complete boundary.

Take the shortest block of the boundary (retrieved by extracting the top of the min-heap) and consider a neighboring cell.

• We know that, in all directions, there is a block that is at least as high as the block we extracted from the heap. This was by design.

[darwinrlo]

Algorithm

• Extract the shortest block from the heap.
• Compute the amount of water collected by the cell the block is at.
• Add the neighbors of the block

Processing a cell

• Compute the amount of water collected at the cell.
• After processing a cell, mark it as processed so that it isn't processed again.

Keep track of the tallest block we've extracted from the heap. This is the shortest block in the boundary. We may insert blocks into the heap that are shorter.

[darwinrlo]

Process the blocks from the outside in.

The shortest block along the boundary.

We remember the tallest block we've extracted from the min-heap because we may insert shorter blocks, possibly blocks of height 0, into the min-heap.

If a block is taller in the interior...

[darwinrlo]

When is a block added to the heap?

• It may be added because it was the neighbor of a block we extracted from the heap and processed.
• It may have been added during the initialization of the heap when we added all the blocks along the border of the grid.

[darwinrlo]

We might add a block from the interior that is shorter than anything we've extracted.

The interior of the grid is unexplored. There might be blocks that are shorter than any block we've added to the heap, taller, or the same size. They can be any non-negative height really.

If we add a block that is shorter than anything already in the heap, then that is the block we'll extract on the next iteration.

[darwinrlo]

Explore blocks on the interior of the boundary that are shorter than the boundary -- this will actually collect rain. The amount of water collected at their corresponding cells is unaffected by blocks that are deeper into the interior -- whether they are shorter, taller, or the same size.

[darwinrlo]

We have a variable, called max, that stores the height of the tallest block we've extracted from the min-heap.

If we have to increase max:

• We've extracted all blocks from the heap that are shorter than this height.
  • We've explored all outer cells in the interior of the enclosed space that is demarcated by blocks of height max or higher. All blocks in the queue are now taller.
  • Adding neighboring cells may result in adding shorter blocks.
• All the blocks we've added to the heap are this height or taller.

If we don't have to increase the max upon extracting an element from the heap, it means we have added cells with shorter blocks.

Every block in the outermost unexplored boundary is now taller than the previously greatest observed height. max is the least of these heights.

[darwinrlo]

Cells in the heap with blocks that are taller than or the same in height as max are boundary cells. The other cells are cells just within the boundary.

If we need to update max, it means we've processed all cells just within the boundary that are shorter than or equal to the shortest segment of the boundary.

We process cells from the boundary inward. That is, we compute the amount of water that is collected at these cells. If we update the max, it means we've processed all cells in the outer layer of the enclosed space that are shorter than the shortest segment of the boundary. The taller blocks that remain in the heap form the boundary of a smaller enclosed space.

[darwinrlo]

We've extracted a cell from the heap and it is larger than the max.

This means we have processed all cells reachable from the boundary that are shorter than the shortest segment of the boundary. These cells are not closed off by blocks that are taller than the shortest block of the boundary.

Surrounding blocks of blocks in the heap may have been processed. This algorithm can explore around a tall block.

If a tall block in the heap has unexplored neighbors, it means it was closed off by blocks that were taller than the previous value of max.

[darwinrlo]

This algorithm has the ability to explore multiple enclosed spaces within a grid.

[darwinrlo]

It really is interesting that this algorithm will explore around smaller blocks.

[darwinrlo]

Why can we process cells from the boundary inward?

Cells inward that are shorter/taller don't matter. If they're shorter, we already know that the shortest segment of the boundary is max. So shorter blocks don't reduce the water collected at the current cell. If they're taller, then the amount of water collected is simply limited by max.

This algorithm will process all cells that are not closed off by blocks that are taller than max, flowing around tall blocks that do not close off other blocks, e.g. a single tall block or a line of tall blocks.

[darwinrlo]

The blocks in the heap form a boundary. max is the height of the shortest block in the boundary. We can compute the water collected at cells not closed off by blocks that are taller than the shortest block in the boundary. We do so inward.

[darwinrlo]

When extracting a tall block from the heap, if it didn't close anything off, all surrounding cells would have been processed.

[darwinrlo]

What happens if there are multiple (say, two) enclosed spaces within the grid?

The blocks of one space are strictly taller than the blocks of the other enclosed space. Then the enclosed space with the shorter blocks will be handled first.

The one with the shorter shortest boundary block is processed first.

If they're the same, they might be processed simultaneously, which should be without issues.

[darwinrlo]

There are so many cases in this problem!

[darwinrlo]

Time: O(mn*log (mn)) Space: O(mn)