algoadvance

Leetcode 417. Pacific Atlantic Water Flow

Problem Statement

You are given an m x n grid of integers representing the height of each cell in a matrix. Water can flow from each cell to any of the 4 neighboring cells: north, south, west, or east, if the neighboring cell’s height is less than or equal to the current cell’s height. Water can flow from a cell to either the Pacific Ocean or the Atlantic Ocean.

The Pacific Ocean touches the left and top edges of the matrix, and the Atlantic Ocean touches the right and bottom edges of the matrix.

Return a list of grid coordinates where water can flow to both the Pacific and Atlantic oceans.

Example:

Given the following 5x5 matrix:

 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]
 ]

Return:
 [
   [0, 4],
   [1, 3],
   [1, 4],
   [2, 2],
   [3, 0],
   [3, 1],
   [4, 0]
 ]

Clarifying Questions

  1. Input Constraints:
    • What are the possible dimensions for the matrix?
      • The matrix dimensions can be from 1x1 to 200x200.
    • Are the heights always positive integers?
      • Yes, the heights are always positive integers.
  2. Edge Cases:
    • What if the matrix is empty?
      • There would be no cells from which the water can flow, hence the return should be an empty list.
    • How to handle corner cases where the matrix size is 1x1?

Strategy

  1. Approach:
    • Use Depth First Search (DFS) or Breadth First Search (BFS) from the cells that are on the edges connected to the Pacific and Atlantic oceans.
    • Create two boolean matrices to record cells that can flow to the Pacific and the Atlantic respectively.
    • Perform DFS/BFS starting from each cell touching the Pacific and mark cells where water can flow from the Pacific.
    • Similarly, perform DFS/BFS for cells touching the Atlantic.
    • The cells that have flow paths to both oceans are the common cells in both boolean matrices.
  2. Algorithm:
    • Initialize two matrices, pacific and atlantic, to keep track of cells from which water can flow to the respective oceans.
    • Perform DFS for all cells adjacent to the Pacific (top and left borders) and mark reachable cells in the pacific matrix.
    • Perform DFS for all cells adjacent to the Atlantic (bottom and right borders) and mark reachable cells in the atlantic matrix.
    • The result will be the intersection of cells marked true in both pacific and atlantic.
  3. DFS Details:
    • For DFS, use a recursive function that propagates to neighboring cells if the neighbor’s height is greater than or equal to the current cell’s height.
    • Continue the propagation until all possible cells are visited that can be reached via the height constraints.

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        if (heights.empty()) return {};
        
        int rows = heights.size();
        int cols = heights[0].size();
        vector<vector<bool>> pacific(rows, vector<bool>(cols, false));
        vector<vector<bool>> atlantic(rows, vector<bool>(cols, false));
        vector<vector<int>> result;
        
        for (int i = 0; i < rows; ++i) {
            dfs(heights, pacific, i, 0);
            dfs(heights, atlantic, i, cols - 1);
        }
        
        for (int j = 0; j < cols; ++j) {
            dfs(heights, pacific, 0, j);
            dfs(heights, atlantic, rows - 1, j);
        }
        
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.push_back({i, j});
                }
            }
        }
        
        return result;
    }
    
private:
    void dfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, int i, int j) {
        int rows = heights.size();
        int cols = heights[0].size();
        visited[i][j] = true;
        vector<vector<int>> directions = \{\{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        
        for (const auto& dir : directions) {
            int ni = i + dir[0], nj = j + dir[1];
            if (ni >= 0 && ni < rows && nj >= 0 && nj < cols 
                && !visited[ni][nj] && heights[ni][nj] >= heights[i][j]) {
                dfs(heights, visited, ni, nj);
            }
        }
    }
};

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI