417. Pacific Atlantic Water Flow

📝 Problem Details

• Title: 417. Pacific Atlantic Water Flow
• Link: https://leetcode.com/problems/pacific-atlantic-water-flow/
• Difficulty: Medium
• Tags/Categories: Graphs BFS Multi-Source-BFS

m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean Pacific Ocean : touches the islands left and top edges Atlantic Ocean: touches the islands right and bottom edges

💭What Were My Initial Thoughts?

- we can work backward, from each cell on the boundary of the pacific and atlantic oceans (the top and left boundaries) (the bottom and right) 
- for each cell on these boundaries, perform a bfs that marks cells as accessible to these oceans 
- we would need two data structures that stores their index positions of these cells for each ocean 
- then we could compare the two structures to see overlaps and return a vector of these positions

🤔What Did I Struggle With?

originally thought of DFS approach which would result in a lot of unecessary recomputation

💡 Explanation of Solution

1. Initalize two matrices (pacific / atlantic) to track whether a cell can reach each ocean

2. Multi-Source BFS:
	- Start from Pacific boundary (top & left)
	- Start from Atlantic boundary (bottom & right)
	- Use BFS from all boundary cells at once to mark reachable cells

3. Find cells accessible to both oceans
	- Iterate through the grid and collect positions that are marked true in both pacific and atlantic

⌛ Complexity Analysis

Time Complexity: O(n*m)
Space Complexity: O(n*m)

💻 Implementation of Solution

class Solution {
private:
    void bfs(vector<vector<int>>& heights, queue<pair<int, int>>& q, vector<vector<bool>>& visited) {
        int rows = heights.size();
        int cols = heights[0].size();
        vector<pair<int,int>> directions = {
            {1,0}, // up
            {-1,0}, // down
            {0,1}, // right
            {0,-1} // left
        };
 
        while(!q.empty()) {
            auto[row, col] = q.front();
            q.pop();
 
            for(auto[dr,dc] : directions) {
                int newRow = row + dr;
                int newCol = col + dc;
 
                // check if in bounds
                // check if new cell has higher or equal height
                if(newRow >= 0 && newRow < rows
                && newCol >=0 && newCol < cols
                && !visited[newRow][newCol] 
                && heights[newRow][newCol] >= heights[row][col]) {
                    
                    // mark the cell as visited
                    visited[newRow][newCol] = true;
                    // push to queue to continue search down that path
                    q.push({newRow, newCol});
                }
            }
        }
    }
 
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        // edge case: empty matrix
        if(heights.empty()) return {};
 
        // init traversal vars
        int rows = heights.size();
        int cols = heights[0].size();
 
        // init tracking grids
        vector<vector<bool>> pacific(rows, vector<bool>(cols, false));
        vector<vector<bool>> atlantic(rows, vector<bool>(cols, false));
 
        // init BFS queues for atlantic and pacific traversal
        queue<pair<int,int>> pacificQueue, atlanticQueue;
 
        // initalize queue with ocean boundary cells
        for(int r = 0; r < rows; r++) {
            pacificQueue.push({r,0}); // left - first element in the row
            atlanticQueue.push({r, cols - 1});  // right - last element in the row
            // we know for certain that boundary cells can reach the ocean
            pacific[r][0] = true;
            atlantic[r][cols-1] = true;
        }
 
        for(int c = 0; c < cols; c++) {
            pacificQueue.push({0,c}); // up - first element in the col
            atlanticQueue.push({rows-1, c}); // down - last element in col
            // we know for certain that boundary cells can reach the ocean
            pacific[0][c] = true;
            atlantic[rows - 1][c] = true;
        }
 
        // perform bfs for both oceans
        bfs(heights, pacificQueue, pacific);
        bfs(heights, atlanticQueue, atlantic);
 
        // find cells that can reach both oceans
        vector<vector<int>> result;
        for(int r = 0; r < rows; r++) {
            for(int c = 0; c < cols; c++) {
                if(pacific[r][c] && atlantic[r][c]) {
                    result.push_back({r,c});
                }
            }
        }
        return result;
    }
};