417. Pacific Atlantic Water Flow – Leetcode Solutions

December 3, 2024

Table of Contents

Description

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell’s height is less than or equal to the current cell’s height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [r_i, c_i] denotes that rain water can flow from cell (r_i, c_i) to both the Pacific and Atlantic oceans.

Examples:

Example 1:

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean 
       [0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean 
       [1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean 
       [1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean 
       [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean 
       [3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean 
       [3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean 
       [4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.

Example 2:

Input: heights = [[1]]
Output: [[0,0]]
Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.

Solution in Python

The problem involves finding cells in a grid that can flow to both the Pacific and Atlantic oceans. We can solve this problem efficiently using a graph traversal technique like Depth First Search (DFS) or Breadth First Search (BFS). Here’s how the solution can be constructed:

Key Observations:

Grid Constraints:
- Water flows from a higher or equal height cell to a lower or equal height cell.
- The Pacific Ocean touches the left and top edges of the grid.
- The Atlantic Ocean touches the right and bottom edges of the grid.
Flow Concept:
- A cell can flow to the Pacific if it can reach the left or top edges.
- A cell can flow to the Atlantic if it can reach the right or bottom edges.
Reverse Traversal:
- Instead of starting from each cell and trying to flow to the oceans, we can reverse the process:
  - Start from the edges (Pacific and Atlantic borders) and determine which cells can flow back to these oceans.
Intersection of Reachable Cells:
- Using two separate traversals for the Pacific and Atlantic oceans, we can find the cells that are common to both.

Approach:

Perform a DFS or BFS starting from all cells adjacent to the Pacific Ocean and mark the cells that can flow to it.
Perform another DFS or BFS starting from all cells adjacent to the Atlantic Ocean and mark the cells that can flow to it.
The result is the intersection of the two sets of cells.

Python

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        # Get dimensions of the grid
        if not heights or not heights[0]:
            return []
        m, n = len(heights), len(heights[0])
        
        # Create visited sets for Pacific and Atlantic oceans
        pacific_reachable = set()
        atlantic_reachable = set()
        
        # Helper function for DFS traversal
        def dfs(row, col, reachable_set):
            # Add the cell to the reachable set
            reachable_set.add((row, col))
            
            # Explore neighbors (up, down, left, right)
            directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
            for dr, dc in directions:
                new_row, new_col = row + dr, col + dc
                # Check if the new cell is within bounds, not visited, and has height >= current cell
                if (0 <= new_row < m and 0 <= new_col < n and
                    (new_row, new_col) not in reachable_set and
                    heights[new_row][new_col] >= heights[row][col]):
                    dfs(new_row, new_col, reachable_set)
        
        # Perform DFS from all Pacific-bordering cells
        for r in range(m):
            dfs(r, 0, pacific_reachable)  # Left edge (Pacific)
            dfs(r, n - 1, atlantic_reachable)  # Right edge (Atlantic)
        for c in range(n):
            dfs(0, c, pacific_reachable)  # Top edge (Pacific)
            dfs(m - 1, c, atlantic_reachable)  # Bottom edge (Atlantic)
        
        # Find the intersection of cells reachable by both oceans
        result = list(pacific_reachable & atlantic_reachable)
        return result

Explanation of the Code:

Initialization:
- pacific_reachable and atlantic_reachable store cells reachable from the Pacific and Atlantic oceans, respectively.
DFS Function:
- The dfs function explores all valid neighboring cells that have a height greater than or equal to the current cell, adding them to the reachable set.
Edge Traversal:
- Perform DFS from the edges of the grid:
  - Pacific: Left and top edges.
  - Atlantic: Right and bottom edges.
Intersection:
- The cells that can flow to both oceans are in the intersection of pacific_reachable and atlantic_reachable.

Solution in C++

C++

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        // Dimensions of the grid
        int m = heights.size();
        int n = heights[0].size();

        // Directions for moving in the grid (up, down, left, right)
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        // Helper function to perform BFS and mark reachable cells
        auto bfs = [&](queue<pair<int, int>>& q, vector<vector<bool>>& ocean) {
            while (!q.empty()) {
                auto [row, col] = q.front();
                q.pop();

                // Traverse in all 4 directions
                for (auto [dr, dc] : directions) {
                    int newRow = row + dr;
                    int newCol = col + dc;

                    // Check if the new cell is within bounds, not visited yet,
                    // and its height is >= the current cell's height
                    if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
                        !ocean[newRow][newCol] && heights[newRow][newCol] >= heights[row][col]) {
                        ocean[newRow][newCol] = true;
                        q.emplace(newRow, newCol);
                    }
                }
            }
        };

        // Create boolean grids to track cells that can reach Pacific and Atlantic
        vector<vector<bool>> pacific(m, vector<bool>(n, false));
        vector<vector<bool>> atlantic(m, vector<bool>(n, false));

        // Queues to manage BFS for both oceans
        queue<pair<int, int>> pacificQueue;
        queue<pair<int, int>> atlanticQueue;

        // Initialize the borders for both oceans
        for (int i = 0; i < m; ++i) {
            pacific[i][0] = true; // Pacific touches the left edge
            atlantic[i][n - 1] = true; // Atlantic touches the right edge
            pacificQueue.emplace(i, 0);
            atlanticQueue.emplace(i, n - 1);
        }
        for (int j = 0; j < n; ++j) {
            pacific[0][j] = true; // Pacific touches the top edge
            atlantic[m - 1][j] = true; // Atlantic touches the bottom edge
            pacificQueue.emplace(0, j);
            atlanticQueue.emplace(m - 1, j);
        }

        // Perform BFS for both oceans
        bfs(pacificQueue, pacific);
        bfs(atlanticQueue, atlantic);

        // Collect cells that can flow to both oceans
        vector<vector<int>> result;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.push_back({i, j});
                }
            }
        }

        return result;
    }
};

Solution in Javascript

JavaScript

var pacificAtlantic = function(heights) {
    // Edge case: if the heights array is empty, return an empty result
    if (!heights || heights.length === 0) return [];

    const rows = heights.length; // Number of rows in the matrix
    const cols = heights[0].length; // Number of columns in the matrix

    // Create two matrices to keep track of cells that can reach the Pacific and Atlantic oceans
    const pacificReachable = Array.from({ length: rows }, () => Array(cols).fill(false));
    const atlanticReachable = Array.from({ length: rows }, () => Array(cols).fill(false));

    // Helper function for Depth-First Search (DFS)
    const dfs = (row, col, reachableMatrix, prevHeight) => {
        // Boundary conditions: ensure the cell is within bounds
        if (
            row < 0 || col < 0 || row >= rows || col >= cols ||
            reachableMatrix[row][col] || // Already visited this cell
            heights[row][col] < prevHeight // Current cell height is lower than the previous one
        ) {
            return;
        }

        // Mark the current cell as reachable
        reachableMatrix[row][col] = true;

        // Perform DFS on all four directions
        dfs(row + 1, col, reachableMatrix, heights[row][col]); // Down
        dfs(row - 1, col, reachableMatrix, heights[row][col]); // Up
        dfs(row, col + 1, reachableMatrix, heights[row][col]); // Right
        dfs(row, col - 1, reachableMatrix, heights[row][col]); // Left
    };

    // Start DFS from all cells adjacent to the Pacific Ocean
    for (let col = 0; col < cols; col++) {
        dfs(0, col, pacificReachable, heights[0][col]); // Top row
        dfs(rows - 1, col, atlanticReachable, heights[rows - 1][col]); // Bottom row
    }

    for (let row = 0; row < rows; row++) {
        dfs(row, 0, pacificReachable, heights[row][0]); // Left column
        dfs(row, cols - 1, atlanticReachable, heights[row][cols - 1]); // Right column
    }

    // Collect cells that can reach both oceans
    const result = [];
    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            if (pacificReachable[row][col] && atlanticReachable[row][col]) {
                result.push([row, col]);
            }
        }
    }

    return result;
};

Solution in Java

Java

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        // Base case: if the matrix is empty, return an empty list
        if (heights == null || heights.length == 0 || heights[0].length == 0) {
            return new ArrayList<>();
        }
        
        int m = heights.length; // Number of rows
        int n = heights[0].length; // Number of columns
        
        // To keep track of visited cells for Pacific and Atlantic
        boolean[][] pacificVisited = new boolean[m][n];
        boolean[][] atlanticVisited = new boolean[m][n];
        
        // Result list to store coordinates
        List<List<Integer>> result = new ArrayList<>();
        
        // Perform DFS for all cells on the borders
        for (int i = 0; i < m; i++) {
            dfs(heights, pacificVisited, i, 0); // Left edge (Pacific)
            dfs(heights, atlanticVisited, i, n - 1); // Right edge (Atlantic)
        }
        
        for (int j = 0; j < n; j++) {
            dfs(heights, pacificVisited, 0, j); // Top edge (Pacific)
            dfs(heights, atlanticVisited, m - 1, j); // Bottom edge (Atlantic)
        }
        
        // Collect cells that can reach both oceans
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacificVisited[i][j] && atlanticVisited[i][j]) {
                    List<Integer> cell = new ArrayList<>();
                    cell.add(i);
                    cell.add(j);
                    result.add(cell);
                }
            }
        }
        
        return result;
    }

    // Helper method for DFS traversal
    private void dfs(int[][] heights, boolean[][] visited, int x, int y) {
        int m = heights.length;
        int n = heights[0].length;
        
        // Mark the current cell as visited
        visited[x][y] = true;
        
        // Define directions for moving in the grid (up, down, left, right)
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        // Traverse to neighboring cells
        for (int[] dir : directions) {
            int newX = x + dir[0];
            int newY = y + dir[1];
            
            // Check if the neighbor is within bounds, not visited, and has height >= current cell
            if (newX >= 0 && newX < m && newY >= 0 && newY < n &&
                !visited[newX][newY] && heights[newX][newY] >= heights[x][y]) {
                dfs(heights, visited, newX, newY);
            }
        }
    }
}

417. Pacific Atlantic Water Flow – Leetcode Solutions

Description

Solution in Python

Key Observations:

Approach:

Explanation of the Code:

Solution in C++

Solution in Javascript

Solution in Java

Popular

38. Count and Say – Leetcode Solutions

The subprocess Module in Python

309. Best Time to Buy and Sell Stock with Cooldown – Leetcode Solutions

173. Binary Search Tree Iterator – Leetcode Solutions

221. Maximal Square – Leetcode Solutions

191. Number of 1 Bits – Leetcode Solutions

140. Word Break II – Leetcode Solutions

417. Pacific Atlantic Water Flow – Leetcode Solutions

Description

Solution in Python

Key Observations:

Approach:

Explanation of the Code:

Solution in C++

Solution in Javascript

Solution in Java

Related Post

Popular