Hard

Quiz

#407 Trapping Rain Water II

APPROACH

Given an m x n integer elevation matrix heightMap, compute how much water accumulates after rainfall. Water flows between horizontally or vertically adjacent cells with equal or lower height, and border cells drain freely. Return the total volume of trapped water.

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

1 of 4

1:00

What is the optimal approach for this problem?