Pacific Atlantic Water Flow

Problem

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.

Examples

Example 1:

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

Example 2:

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

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

Constraints

• 1 <= heights.length, heights[r].length <= 100
• 0 <= heights[r][c] <= 1000

You should aim for a solution with O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the grid.

Solution

Perform BFS separately for Pacific and Atlantic. Open starts off with the shoreline, and we search backwards checking if height stays the same or increases.

class Solution {
    using Cell = std::pair<int, int>;
    using Open = std::queue<Cell>;
    static inline std::array<Cell, 4> OFFSETS = {{
        {-1, 0}, {1, 0}, {0, -1}, {0, 1}
    }};
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        const int ROWS = heights.size();
        const int COLS = heights[0].size();
        Open open;
        
        auto bfs = [&](Open &open, std::vector<bool> &closed) {
            while (!open.empty()) {
                auto [r, c] = open.front();
                open.pop();
                for (const auto &[dr, dc] : OFFSETS) {
                    auto row = r + dr;
                    auto col = c + dc;
                    // Out of bounds
                    if (row < 0 || col < 0 || row >= ROWS || col >= COLS) {
                        continue;
                    }
                    // Allready considerd
                    if (closed[row * COLS + col]) {
                        continue;
                    }
                    // Add if up hill
                    if (heights[row][col] >= heights[r][c]) {
                        closed[row * COLS + col] = true;
                        open.emplace(row, col);
                    }
                }
            }
        };
 
        std::vector<bool> pacific(ROWS * COLS, false);
        for (int r = 0; r < ROWS; ++r) {
            pacific[COLS * r] = true;
            open.emplace(r, 0);
        }
        for (int c = 1; c < COLS; ++c) {
            pacific[c] = true;
            open.emplace(0, c);
        }
        bfs(open, pacific);
 
        std::vector<bool> atlantic(ROWS * COLS, false);
        for (int r = 0; r < ROWS; ++r) {
            atlantic[COLS * r + COLS - 1] = true;
            open.emplace(r, COLS - 1);
        }
        for (int c = 0; c < COLS - 1; ++c) {
            atlantic[(ROWS - 1) * COLS + c] = true;
            open.emplace(ROWS - 1, c);
        }
        bfs(open, atlantic);
 
        // Result only contains if true for both
        std::vector<std::vector<int>> cells;
        for (int r = 0; r < ROWS; ++r) {
            for (int c = 0; c < COLS; ++c) {
                const auto idx = r * COLS + c;
                if (pacific[idx] && atlantic[idx]) {
                    std::vector<int> cell = {r, c};
                    cells.push_back(std::move(cell));
                }
            }
        }
        return cells;
    }
};