Concise C++ method with explanation
It takes me a long time to figure it out, but actually the idea is quite straightforward. Imagine the pool is surrounded by many bars. The water can only go out
It takes me a long time to figure it out, but actually the idea is quite straightforward. Imagine the pool is surrounded by many bars. The water can only go out from the lowest bar. So we always start from the lowest boundary and keep pushing the bar from boundary towards inside. It works as if we are replacing the old bars with a bar higher than it.\nSee the following simple example:\n4 4 4 4\n4 0 1 2\n4 4 4 4\nit looks like we push the bar of 2 towards left and record the difference. Then you can use the same procedure with the following figure\n4 4 4 4\n4 0 2 2\n4 4 4 4\n```\n    int trapRainWater(vector<vector<int>>& heightMap) {\n        typedef pair<int,int> cell;\n        priority_queue<cell, vector<cell>, greater<cell>> q;\n        int m = heightMap.size();\n        if (m == 0) return 0;\n        int n = heightMap[0].size();\n        vector<int> visited(m*n, false);\n        \n        for (int i = 0; i < m; ++i)\n        for (int j = 0; j < n; ++j) {\n            if (i == 0 || i == m-1 || j == 0  || j == n-1) {\n                if (!visited[i*n+j])\n                    q.push(cell(heightMap[i][j], i*n+j));\n                visited[i*n+j] = true;\n            }\n        }\n        \n        int dir[4][2] = {{0,1}, {0, -1}, {1, 0}, {-1, 0}};\n        int ans = 0;\n        while(!q.empty()) {\n            cell c = q.top();\n            q.pop();\n            int i = c.second/n, j = c.second%n;\n            \n            for (int r = 0; r < 4; ++r) {\n                int ii = i+dir[r][0], jj = j+dir[r][1];\n                if (ii < 0 || ii >= m || jj < 0 || jj >= n || visited[ii*n+jj])\n                    continue;\n                ans += max(0, c.first - heightMap[ii][jj]);\n                q.push(cell(max(c.first, heightMap[ii][jj]), ii*n+jj));\n                visited[ii*n+jj] = true;\n            }\n        }\n        return ans;\n    }\n```
[]