No code. Explanation of priority queue solution
Coming from Trapping Water I\nAlright. So most people who try out Trapping Rain Water II after solving Trapping Rain Water I (including myself) reason out that 
**Coming from Trapping Water I**\nAlright. So most people who try out Trapping Rain Water II after solving Trapping Rain Water I (including myself) reason out that the problem is similar except that now you need to check 4 directions compared to 2 directions (left and right) for each point. This infact is incorrect as in 2D, water can flow out of diagonally as well. Therefore, the amount of water that can be stored above a grid element depends on its neighboring rows and columns as well. A simple example to see which this might be the case, check this example out\n```\n1 1 1 1 1 1 1\n1 1 0 0 0 1 1\n1 0 1 1 1 0 1\n1 1 0 0 0 1 1\n1 1 1 1 1 1 1\n```\nSo for any grid item of height 0, you can see that water flows into the 0 cells along its 8 adjacent directions. And this gets even more complicated to keep track with varying heights instead of having just 0 and 1.\n\n**So how do you solve it**\nThe key observation to solving this problem comes from understanding that to be able to hold any sort of water over a grid element, you need one of the elements inside the grid to lie at a lower point and the lowest boundary of this low point dictates how much water it can hold. So we go ahead and put the boundary of the grid in a priority queue.\n\nNow what we do is, we pick the smallest element (call it **A**) out of the boundary. If its neighbor (call it **B**) is at a higher point than **A**, then **B** becomes a new part of the boundary. Think of it like this. Imagine you had a lake surrounded by two walls. The outer wall is the smaller wall **A** and the inner wall **B** is the higher wall, the amount of water stored in the lake is dictated by the higher inner wall **B**. So we add our grid element **B** to our priority queue. \n\nNow of the other case. When **A** is greater than **B**. Lets go through this part slowly. We claimed **A** to be the smallest part of our boundary. Every other boundary is larger than **A**.  And if you recall the observation we made earlier "`The key observation to solving this problem comes from understanding that to be able to hold any sort of water over a grid element, you need one of the elements inside the grid to lie at a lower point and the lowest boundary of this low point dictates how much water it can hold.`" There we go! Since **A** is the lowest boundary that point **B** can have, **B** will have **B - A** amount of water above it. And to any other point around **B**, the height of **A** will still be the boundary for it (since **B** is covered by **A**, if there is a point around **B**, lower than **B**, (call this point **C**); **A** will still be the boundary for **C**) (If this point wasn\'t clear, think of when you are trying to store water in between a stairs like structure. \n```\n3 2 1 0 1 2 3 \n```\nIf these are the heights of the stairs, the amount of water stored by `1` is not dictated by `2`. It\'s dictated by `3` since `3` is the boundary for `1` and not `2`
['Heap (Priority Queue)']