Swim in Rising Water

You can simply just run a breadth-first search starting from grid[0][0]. Everytime, you stumble upon a new square, you can mark it as seen in the seen matrix, and update its value in grid if the current square is smaller. We can then place the new square into a min heap, sorted based on its water level, and repeat until seen.back.back == 1.

code

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
        vector<vector<int>> seen (m, vector<int>(n, 0));
        seen[0][0] = 1;
        pq.push({grid[0][0], {0, 0}});

        while(seen.back().back() == 0) {
            auto top = pq.top();
            pq.pop();

            for (int i = 0; i < 4; ++i) {
                int X = top.second.first;
                int Y = top.second.second;
                int newX = X + direction[i][0];
                int newY = Y + direction[i][1];

                if (newX >= 0 && newY >= 0 && newX < m && newY < n && seen[newX][newY] == 0) {
                    grid[newX][newY] = max(grid[newX][newY], grid[X][Y]);
                    pq.push({grid[newX][newY], {newX, newY}});
                    seen[newX][newY] = 1;
                }
            }
        }

        return grid.back().back();
    }
private:
    vector<vector<int>> direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
};

complexity

• Time: O(n^2 log(n)) where n denotes the number of elements inside of grid
• Space: O(n^2)

time taken

• 21 minutes and 11 seconds