Pacific Atlantic Water Flow: Exploring Water Movement in a Matrix

The "Pacific Atlantic Water Flow" problem is a unique challenge that combines elements of graph theory and depth-first search (DFS) in a matrix setting.

Problem Statement

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, determine the list of grid coordinates where water can flow to both the Pacific and Atlantic oceans. Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Example

Consider a matrix: Pacific ~ ~ ~ ~ ~ ~ 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 *

• • • • Atlantic

The cells marked with * are the ones where water can flow to both oceans.

Depth-First Search Solution

Breaking Down the Solution

• Initialize Oceans: Create two matrices, pacific and atlantic, to track the cells reachable from each ocean.
• Depth-First Search: Perform DFS from the edges of the matrix towards the interior. Mark cells reachable from each ocean in their respective matrices.
• Collect Results: Iterate over the entire matrix, and for each cell reachable from both oceans, add its coordinates to the result list.

Conclusion

The Pacific Atlantic Water Flow problem showcases the application of DFS in matrix traversal and is an excellent example of how to handle complex flow and reachability problems in a grid. It emphasizes depth-first search's versatility in exploring paths and conditions in a matrix.

Rust Solution

Rust's usize/i32 split drives all the casting here: lengths arrive as heights.len() as i32 so the bounds checks (nr >= 0, nr < m) can run on signed values, then every grid access casts back with as usize. The nested fn dfs is a plain function, not a closure, so it cannot capture the surrounding scope — heights, m, and n are threaded through as explicit parameters, with ocean: &mut Vec<Vec<bool>> taken by mutable borrow so the DFS marks reachability in place and heights: &Vec<Vec<i32>> taken by shared borrow. The vec![vec![false; n as usize]; m as usize] macro builds the two reachability grids in one expression, and coordinates accumulate via result.push(vec![i, j]).

Go Solution

Go's recursive closure needs the two-step form: var dfs func(r, c int, ocean [][]bool) is declared first so that dfs = func(...) can reference dfs from inside its own body, which a single := binding could not do. The 2D bool grids are allocated row by row — make([][]bool, m) then a range loop calling make([]bool, n) per row — since Go has no single-expression 2D allocation. Directions live in a fixed [4][2]int array walked with for _, d := range dirs, and var result [][]int starts as a nil slice that append grows, so a matrix with no qualifying cell returns nil rather than an empty slice.