Java Beats 99.75% with Explanation (No Priority Queue or Extra Classes) Simple Solution
Intuition\nInstead of calculating how much water will fit in each cell, we can first fill all cells except the borders with the maximum amount of water and then
# Intuition\nInstead of calculating how much water will fit in each cell, we can first fill all cells except the borders with the maximum amount of water and then drain the excess water from each cell\n\n# Algorithm\nFirst, let\'s create `waterLevelMap` 2D int array where we will store the water level for each cell. \nThen fill all of its bounds (the first and last row and column) with values from the same cells of the `heighMap` array, because there is no way water can stay on these cells, and assign the remaining cells the maximum possible water level (20,000).\nNow all we have to do is drain the excess water.\n\nTo do this, we create a cycle in which we go through all the matrix elements (except for borders) first from top to bottom from left to right, then in the opposite direction (from bottom to top from right to left).\nFor each cell, check the following: \n\u2013 if there is water in the cell (`waterLevelMap[j][i] > heightMap[j][i]`), then check that the water level in this cell does not exceed the water level in the two neighboring cells, which are on the opposite side from the direction of the traversal. If the water level of current cell is higher than the one we are comparing to, we assign current cell the water level of the comparing cell (since the water level of the cell cannot be lower than its height, we pick the maximum of the water level of the comparing cell and the height of the current cell)\n\u2013 when making a backward traversal, after checking the water level in the current cell we also check if among the two already passed neighboring cells there are those from which it is still necessary to drain the excess water (that is, their water level is higher than in the current cell). If there are still such cells, we get to the next iteration of the cycle. Otherwise the cycle ends\n\nOnce the cycle is complete, we can be sure that all the excess water has already drained away, and all we have to do is simply summarize the amount of water that has been trapped in each cell (`waterLevelMap[i][j] - heightMap[i][j]`). This sum will be the answer.\n\n\n# Examples\n- let X = maximum possible water level (20,000).\n\n\u2013 Example 1 (from the problem description):\n\n.&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; waterLevelMap &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;waterLevelMap \nheightsMap &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; waterLevelMap &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; after 1st traversal &nbsp; &nbsp; &nbsp; &nbsp;  after backward traversal\n.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;before cycle &nbsp; &nbsp; &nbsp; &nbsp; (1/2 cycle completed) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;(cycle completed)\n\n1&nbsp; 4&nbsp; 3&nbsp; 1&nbsp; 3&nbsp; 2&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1&nbsp; 4&nbsp; 3&nbsp; 1&nbsp; 3&nbsp; 2 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1&nbsp; 4&nbsp; 3&nbsp; 1&nbsp; 3&nbsp; 2 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1&nbsp; 4&nbsp; 3&nbsp; 1&nbsp; 3&nbsp; 2\n3&nbsp; 2&nbsp; 1&nbsp; 3&nbsp; 2&nbsp; 4 &nbsp; &nbsp;->&nbsp; &nbsp; 3&nbsp; X&nbsp; X&nbsp; X&nbsp; X&nbsp; 4 &nbsp; &nbsp; -> &nbsp; &nbsp; 3&nbsp; 3&nbsp; 3&nbsp; 3&nbsp; 3&nbsp; 4 &nbsp; &nbsp; &nbsp;  &nbsp;->&nbsp; &nbsp;&nbsp; &nbsp; 3&nbsp; 3&nbsp; 3&nbsp; 3&nbsp; 3&nbsp; 4\n2&nbsp; 3&nbsp; 3&nbsp; 2&nbsp; 3&nbsp; 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 2&nbsp; 3&nbsp; 3&nbsp; 2&nbsp; 3&nbsp; 1 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 2&nbsp; 3&nbsp; 3&nbsp; 2&nbsp; 3&nbsp; 1 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 2&nbsp; 3&nbsp; 3&nbsp; 2&nbsp; 3&nbsp; 1\n\nAs we can see, in this simple example the correct water level has already been reached after half of the cycle. \nThe answer (difference between waterLevelMap and heightMap) is 4.\n\n\u2013 Example 2:\n\n.&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; waterLevelMap &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;waterLevelMap \nheightsMap &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; waterLevelMap &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; after 1st traversal &nbsp; &nbsp; &nbsp; &nbsp;  after backward traversal\n.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;before cycle &nbsp; &nbsp; &nbsp; &nbsp; (1/2 cycle completed) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;(cycle completed)\n\n4&nbsp; 2&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 2&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 2&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 2&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4\n4&nbsp; 1&nbsp; 4&nbsp; 2&nbsp; 2&nbsp; 4&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; X&nbsp; X&nbsp; X&nbsp; X&nbsp; 4&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 2&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 2&nbsp; 4&nbsp; 3&nbsp; 3&nbsp; 4\n4&nbsp; 1&nbsp; 4&nbsp; 4&nbsp; 3&nbsp; 4 &nbsp; &nbsp;->&nbsp; &nbsp; 4&nbsp; X&nbsp; X&nbsp; X&nbsp; X&nbsp; 4 &nbsp; &nbsp; -> &nbsp; &nbsp; 4&nbsp; 2&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4 &nbsp; &nbsp; &nbsp;  &nbsp;->&nbsp; &nbsp;&nbsp; &nbsp; 4&nbsp; 2&nbsp; 4&nbsp; 4&nbsp; 3&nbsp; 4\n4&nbsp; 1&nbsp; 2&nbsp; 1&nbsp; 2&nbsp; 4&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; X&nbsp; X&nbsp; X&nbsp; X&nbsp; 4&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 2&nbsp; 2&nbsp; 2&nbsp; 2&nbsp; 4 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 2&nbsp; 2&nbsp; 2&nbsp; 2&nbsp; 4\n4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4\n\nIn this more complex example, the spiral structure from which we need to drain begins just where the cycle begins its first traversal, so we still only need one iteration of the cycle.\nThe answer is 6.\n\n\u2013 Example 3:\nNow let\'s rotate the field from the previous example 180 degrees and see what happens:\n\n.&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; waterLevelMap &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;waterLevelMap \nheightsMap &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; waterLevelMap &nbsp; &nbsp; &nbsp; after 1st cycle iteration&nbsp; &nbsp; &nbsp; &nbsp;  after 2nd iteration\n.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;before cycle &nbsp; &nbsp; &nbsp; &nbsp;( cycle will continue &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;(cycle completed)\n.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;because a[1][1]<a[2][1] )\n4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4\n4&nbsp; 2&nbsp; 1&nbsp; 2&nbsp; 1&nbsp; 4&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; X&nbsp; X&nbsp; X&nbsp; X&nbsp; 4&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 2&nbsp; 2&nbsp; 2&nbsp; 2&nbsp; 4 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 2&nbsp; 2&nbsp; 2&nbsp; 2&nbsp; 4\n4&nbsp; 3&nbsp; 4&nbsp; 4&nbsp; 1&nbsp; 4 &nbsp; &nbsp;->&nbsp; &nbsp; 4&nbsp; X&nbsp; X&nbsp; X&nbsp; X&nbsp; 4 &nbsp; &nbsp; -> &nbsp; &nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 2&nbsp; 4 &nbsp; &nbsp; &nbsp;  &nbsp;->&nbsp; &nbsp;&nbsp; &nbsp; 4&nbsp; 3&nbsp; 4&nbsp; 4&nbsp; 2&nbsp; 4\n4&nbsp; 2&nbsp; 2&nbsp; 4&nbsp; 1&nbsp; 4&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; X&nbsp; X&nbsp; X&nbsp; X&nbsp; 4&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 2&nbsp; 4 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 3&nbsp; 3&nbsp; 4&nbsp; 2&nbsp; 4\n4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 2&nbsp; 4&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 2&nbsp; 4 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 2&nbsp; 4 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 4&nbsp; 2&nbsp; 4\n\nIn this example, during the backward traversal of the matrix, we find that there is still at least one cell that needs to be drained. So another iteration of the cycle occurs, during which all the excess water drains out.\nThe answer is 6 as well.\nSimilarly, the cycle would work in the case of a larger spiral with several full turns. Each turn would require one more iteration of the cycle. In this case, all branches from the main spiral are unimportant and will be drained at the same time with the main spiral. So the number of iterations of the cycle depends only on the number of turns in the largest spiral.\n# Complexity\n- Time complexity:\nIt depends on the input data:\n\u2013 at best - O(m\\*n)\n\u2013 average - O(m\\*n\\*number_of_turns_of_the_largest_spiral), which is usually O(m\\*n) as well\n\u2013 at worst - O(m\\*n\\*min(m,n)). (If the whole field is one big spiral)\n\n- Space complexity:\nO(m*n), because all we need is one additional two-dimensional array of size m\\*n\n\n# Java Code\n```\nclass Solution {\n    public int trapRainWater(int[][] heightMap) {\n        int trappedWater = 0;\n        int[][] waterLevelMap = new int[heightMap.length][heightMap[0].length];\n\n        for (int i = 1; i < heightMap.length-1; i++) {\n            waterLevelMap[i][0] = heightMap[i][0];\n            for (int j = 1; j < heightMap[i].length-1; j++) {\n                waterLevelMap[i][j] = 20_000;\n            }\n            waterLevelMap[i][heightMap[i].length-1] = heightMap[i][heightMap[i].length-1];\n        }\n        for (int i = 0; i < heightMap[0].length; i++) {\n            waterLevelMap[0][i] = heightMap[0][i];\n            waterLevelMap[heightMap.length-1][i] = heightMap[heightMap.length-1][i];\n        }\n\n        boolean drain = true;\n        while (drain) {\n            drain = false;\n            for (int i = 1; i < heightMap[0].length-1; i++) {\n                for (int j = 1; j < heightMap.length-1; j++) {\n                    if (waterLevelMap[j][i] > heightMap[j][i]) {\n                        if (waterLevelMap[j][i] > waterLevelMap[j][i-1])\n                            waterLevelMap[j][i] = Integer.max(waterLevelMap[j][i-1], heightMap[j][i]);\n                        if (waterLevelMap[j][i] > waterLevelMap[j-1][i])\n                            waterLevelMap[j][i] = Integer.max(waterLevelMap[j-1][i], heightMap[j][i]);\n                    }\n                }\n            }\n            for (int i = heightMap[0].length-2; i > 0; i--) {\n                for (int j = heightMap.length-2; j > 0; j--) {\n                    if (waterLevelMap[j][i] > heightMap[j][i]) {\n                        if (waterLevelMap[j][i] > waterLevelMap[j][i+1])\n                            waterLevelMap[j][i] = Integer.max(waterLevelMap[j][i+1], heightMap[j][i]);\n                        if (waterLevelMap[j][i] > waterLevelMap[j+1][i])\n                            waterLevelMap[j][i] = Integer.max(waterLevelMap[j+1][i], heightMap[j][i]);\n                        if (waterLevelMap[j][i] < waterLevelMap[j][i+1] && waterLevelMap[j][i+1] > heightMap[j][i+1]\n                            || waterLevelMap[j][i] < waterLevelMap[j+1][i] && waterLevelMap[j+1][i] > heightMap[j+1][i])\n                            drain = true;\n                    }\n                }\n            }\n        }\n\n        for (int i = 1; i < waterLevelMap.length-1; i++) {\n            for (int j = 1; j < waterLevelMap[i].length-1; j++) {\n                trappedWater += waterLevelMap[i][j] - heightMap[i][j];\n            }\n        }\n\n        return trappedWater;\n    }\n}\n```
['Matrix', 'Java']