4 min read Algorithm Coding

Neetcode - Pacific Atlantic Water Flow

Neetcode - Pacific Atlantic Water Flow
Photo by Nate Kadlac / Unsplash
Write code that makes sense tomorrow, not just today.

Pacific Atlantic Water Flow

You are given a rectangular island heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The islands borders the Pacific Ocean from the top and left sides, and borders the Atlantic Ocean from the bottom and right sides.

Water can flow in four directions (up, down, left, or right) from a cell to a neighboring cell with height equal or lower. Water can also flow into the ocean from cells adjacent to the ocean.

Find all cells where water can flow from that cell to both the Pacific and Atlantic oceans. Return it as a 2D list where each element is a list [r, c] representing the row and column of the cell. You may return the answer in any order.

Input: heights = [
[4,2,7,3,4],
[7,4,6,4,7],
[6,3,5,3,6]
]

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

Input: heights = [[1],[1]]

Output: [[0,0],[0,1]]

This is an intriguing problem because it involves some non-trivial constraints, rather than just performing a straightforward DFS traversal over the array. I immediately recognized that the boundary cells adjacent to the Pacific and Atlantic Oceans could serve as starting points for the search.

However, I hadn't considered using two separate boolean arrays to track reachability from each ocean and then finding their intersection. This approach was enlightening and taught me a valuable lesson. Here's the code for reference:

class Solution {
  vector<pair<int, int>> directions = {
    {-1, 0},
    {1, 0},
    {0, -1},
    {0, 1}
  };
public:
  vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    int rows = heights.size(), cols = heights[0].size();

    vector<vector<bool>> pacific(rows, vector<bool>(cols, false);
    vector<vector<bool>> atlantic(rows, vector<bool>(cols, false);

    for (int r = 0; r < rows; ++r) {
      dfs(r, 0, heights, pacific);
      dfs(r, cols - 1, heights, atlantic);
    }

    for (int c = 0; c < cols; ++c) {
      dfs(0, c, heights, pacific);
      dfs(rows - 1, c, heights, atlantic);
    }

    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;
  }

  void dfs(int r, int c, 
    vector<vector<int>>& heights, vector<vector<bool>>& ocean) {
      int rows = heights.size();
      int cols = heights[0].size();
    
      if (ocean[r][c]) return;

      ocean[r][c] = true;

      for (auto [dr, dc] : directions) {
          int nr = r + dr;
          int nc = c + dc;
          if (nr >= 0 && nc >= 0 && nr < rows && nc < cols) {
            dfs(nr, nc, heights, ocean);
      }
    }
  }
};

DFS - CSY

From the code above, you can see that we create two separate arrays to track visits from the Pacific and Atlantic Oceans, respectively. A cell is considered part of the final result if it is reachable from both oceans — that is, if it’s marked true in both arrays.

One potentially confusing idea is whether a single high-elevation cell could flow to every other cell, and if that somehow affects cells that otherwise shouldn't be reachable. However, this concern only arises if we were to start the traversal from every cell in the grid. In this problem, we only initiate the search from the borders — specifically, the top and left edges for the Pacific Ocean, and the bottom and right edges for the Atlantic Ocean. This strategy inherently avoids that issue.

Additionally, a BFS-based solution is also provided as an alternative to the DFS approach.

class Solution {
    vector<pair<int, int>> directions = {
        {-1, 0},
        {1, 0},
        {0, -1},
        {0, 1}
    };
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int rows = heights.size(), cols = heights[0].size();

        vector<vector<bool>> pacific(rows, vector<bool>(cols, false));
        vector<vector<bool>> atlantic(rows, vector<bool>(cols, false));

        queue<pair<int, int>> pacQueue, atlQueue;

        for (int r = 0; r < rows; ++r) {
            pacQueue.push({r, 0});
            atlQueue.push({r, cols - 1});
        }

        for (int c = 0; c < cols; ++c) {
            pacQueue.push({0, c});
            atlQueue.push({rows - 1, c});
        }

        bfs(pacQueue, pacific, heights);
        bfs(atlQueue, atlantic, heights);

        vector<vector<int>> answers;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (pacific[r][c] && atlantic[r][c]) {
                    answers.push_back({r, c});
                }
            }
        }

        return answers;
    }

    void bfs(queue<pair<int, int>>& q, 
        vector<vector<bool>>& ocean, 
        vector<vector<int>>& heights) {
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            ocean[r][c] = true;

            for (auto [dr, dc] : directions) {
                int nr = r + dr, nc = c + dc;
                if (
                    nr >= 0 && nr < heights.size() && 
                    nc >= 0 && nc < heights[0].size() && 
                    !ocean[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                    q.push({nr, nc});
                }
            }
        }
    }
};

BFS - Neetcode

Conclusion

Although this problem falls under the Graph category, its solution relies on standard traversal techniques like recursive DFS or BFS, similar to those used in previous graph-related problems. However, what sets it apart is the use of dual traversal from multiple starting points (the ocean borders) and the clever use of two boolean matrices to determine the overlapping reachable cells. This variation adds an interesting layer of complexity beyond a typical single-source traversal.

CSY

CSY

Nagoya, Japan