C++ | 88.70% faster | Using priority queue
The approach here is that we start from the outermost boundary and go on shrinking it from the current weakest link (minimum height). This weakest link concept 
The approach here is that we start from the outermost boundary and go on shrinking it from the current weakest link (minimum height). This weakest link concept can be implemented using a minimum heap priority queue, in which we push the boundary heights and get the minimum each time.\nWe get the trapped water when we find a building with height smaller than the current weakest link, the reason is that when even the weakest link in the boundary is not allowing the water to pass through it, then the water stays. The units of water is the difference in heights of the current weakest link and the other smaller height visited just now.\n```\nclass Solution {\npublic:\n    struct Position {\n        int x;\n        int y;\n        \n        Position (int a = 0, int b = 0) {\n            x = a;\n            y = b;\n        }\n    };\n    \n\t// The height and its position in one place\n    class Height {\n        public:\n            int h;\n            Position position;\n        \n            Height(int p = -1, int a = -1, int b = -1) {\n                h = p;\n                position.x = a;\n                position.y = b;\n            }\n        \n            bool operator<(const Height& h1) const {\n                return h > h1.h;\n            }\n    };\n    \n    int trapRainWater(vector<vector<int>>& heightMap) {\n        priority_queue<Height> minHeap;\n        Height top;\n        \n        int m = heightMap.size();\n        int n = heightMap.size() == 0 ? 0 : heightMap[0].size();\n        \n        vector<vector<bool>> visited(m, vector<bool> (n, 0));\n        \n        int water = 0;\n        \n\t\t// Pushes column boundary in min heap\n        for (int i = 0; i < n; i++) {\n            minHeap.push(Height(heightMap[0][i], 0, i));\n            visited[0][i] = 1;\n            \n            minHeap.push(Height(heightMap[m - 1][i], m - 1, i));\n            visited[m - 1][i] = 1;\n        }\n        \n\t\t// Pushes row boundary in min heap\n        for (int j = 1; j < m - 1; j++) {\n            minHeap.push(Height(heightMap[j][0], j, 0));\n            visited[j][0] = 1;\n            \n            minHeap.push(Height(heightMap[j][n - 1], j, n - 1));\n            visited[j][n - 1] = 1;\n        }\n        \n        while (!minHeap.empty()) {\n            top = minHeap.top();\n            minHeap.pop();\n                     \n            int x = top.position.x, y = top.position.y;            \n            int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n            \n\t\t\t// Checks the directions - top, bottom, right, left for unvisited elements\n            for (int p = 0; p < 4; p++) {\n                int row = x + directions[p][0];\n                int col = y + directions[p][1];\n                \n\t\t\t\t// If a valid unvisited element is found\n                if (row >= 0 && row < m && col >= 0 && col < n && !visited[row][col]) {\n                    Height next(heightMap[row][col], row, col);\n                    \n\t\t\t\t\t// If water can be trapped (when height of this new element is less than the current weakest link) \n                    if (next.h < top.h) {\n                        water += top.h - next.h;                                                \n                        next.h = max(next.h, top.h);\n                    }\n\t\t\t\t\t\n\t\t\t\t\t// Shrinks the boundary by pushing the new element\n                    minHeap.push(next);\n                    visited[row][col] = 1;\n                }   \n            }\n        }\n        \n        return water;\n    }\n};\n
['C']