Using Dijkstra's algorithm Detailed Explanation
🌟 IntuitionThe problem involves finding the amount of water that can be trapped in a 2D grid of elevations. Each cell has a height, and water can only accumulat
# 🌟 Intuition  

The problem involves finding the amount of water that can be trapped in a 2D grid of elevations. Each cell has a height, and water can only accumulate if it is surrounded by higher elevations.  
The key insight is:  
- The amount of water trapped above a cell depends on the **minimum boundary height** around that cell.  
- By processing boundary cells first and moving inward, we ensure that the boundary heights for each cell are accurately computed.

---

# 🛠️ Approach  

## 1. **Graph Representation**  
We treat the grid as a graph where:  
- Each cell is a **node**.  
- Each node is connected to its adjacent neighbors (up, down, left, right) with weights equal to the cell's height.  
- A **virtual start node** is added, connected to all boundary cells, with weight `0`.  

### Example for a 3x3 grid:
heightMap = [ [1, 4, 3], [3, 2, 5], [4, 5, 2] ]

yaml
Copy
Edit
- Cells like `(0,0)` are connected to their neighbors `(0,1)` and `(1,0)`.  
- Boundary cells `(0,0)`, `(0,2)`, `(2,0)`, etc., are connected to the virtual start node.  

---

## 2. **Dijkstra's Algorithm for Boundary Heights**  
- Use a **priority queue (min-heap)** to process cells in increasing order of height.  
- For each cell processed:  
  - Update the minimum boundary height of its neighbors.  
  - If a cell’s height is lower than the current boundary height, it can trap water, and we add the trapped volume.  
  - Add the cell’s updated boundary height back into the heap.

---

# ⏳ Complexity  
### Time Complexity:
- Constructing the graph: O(m * n)
- Processing all cells using Dijkstra's algorithm: O((m * n) * log(m * n))
- **Overall:** O(m * n * log(m * n))

### Space Complexity:
- Graph storage: O(m * n)
- Priority queue: O(m * n)
- **Overall:** O(m * n)


# 💻 Code  
```cpp []
class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        if (heightMap.empty() || heightMap[0].empty()) return 0;

        int rows = heightMap.size(), cols = heightMap[0].size();
        vector<vector<int>> graph(rows * cols + 1);
        int virtualStart = rows * cols;

        // Direction vectors for moving in 4 directions
        vector<int> dx = {0, 0, 1, -1};
        vector<int> dy = {1, -1, 0, 0};

        // Build the graph
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int currentCell = i * cols + j;

                // Connect boundary cells to virtual start node
                if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
                    graph[virtualStart].push_back(currentCell);
                }

                // Connect current cell to its neighbors
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && x < rows && y >= 0 && y < cols) {
                        graph[currentCell].push_back(x * cols + y);
                    }
                }
            }
        }

        // Dijkstra-like BFS to calculate distances
        auto calculateDistances = [&](int start) {
            vector<int> dist(graph.size(), INT_MAX / 2);
            dist[start] = 0;

            // Min-heap to prioritize cells with smaller heights
            set<pair<int, int>> pq; // {distance, node}
            pq.insert({0, start});

            while (!pq.empty()) {
                auto [currentDist, currentNode] = *pq.begin();
                pq.erase(pq.begin());

                for (int neighbor : graph[currentNode]) {
                    int weight = heightMap[neighbor / cols][neighbor % cols];
                    if (max(currentDist, weight) < dist[neighbor]) {
                        pq.erase({dist[neighbor], neighbor});
                        dist[neighbor] = max(currentDist, weight);
                        pq.insert({dist[neighbor], neighbor});
                    }
                }
            }

            return dist;
        };

        vector<int> dist = calculateDistances(virtualStart);

        // Calculate trapped water
        int trappedWater = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int cell = i * cols + j;
                int boundaryHeight = dist[cell];
                if (boundaryHeight > heightMap[i][j]) {
                    trappedWater += boundaryHeight - heightMap[i][j];
                }
            }
        }

        return trappedWater;
    }
};

```
['Breadth-First Search', 'Heap (Priority Queue)', 'C++']