Problem overview
An island is a grid of cells, heights, with m rows and n columns. The Pacific Ocean touches the left and top edges, and the Atlantic Ocean touches the right and bottom edges. Water flows from a cell to a neighbor above, below, left or right when the neighbor's height is less than or equal to the cell's, and from any cell on an edge into the ocean that touches that edge. The function pacific_atlantic returns the cells from which water can reach both oceans, as a vector of [r, c] pairs in reading order: row by row from the top, left to right within a row.
For the grid
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
the answer is [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]. The cell [0, 4] is on the top edge and on the right edge, so it touches both oceans. The cell [2, 2] has height 5, and water runs up to the Pacific through heights 3 and 2, and right to the Atlantic through heights 3 and 1. The cell [2, 1] has height 4 and reaches the Pacific through [2, 0], but every path to the Atlantic needs a step up.
For [[1]] the answer is [[0, 0]], because the single cell touches all four edges. For a ring of 5s around a single 1 the answer is every cell except the middle one: water moves between equal heights, and the 1 is lower than all its neighbors.
The lesson asks for O(m · n) time and O(m · n) extra space.
Approach: climb up from each ocean
The direct idea follows the water down from every cell, one search per cell. That can cost O((m · n)²): think of a large flat lake in the middle of the island, where each cell's search wanders over the whole lake before giving up.
Turn the question around. Start at an ocean and climb. A search that begins on all the cells along an ocean's two edges moves to a neighbor only when the neighbor is at least as high as the current cell. If the neighbor is at least as high, its water can flow down into the current cell, and from there along the same path to the ocean. So every cell the search reaches can send its water to that ocean.
Run this once from the Pacific's edges and once from the Atlantic's edges. The answer is the cells that both searches reach. Each search is a breadth-first search that starts from many cells at once and marks every cell at most once, so each takes O(m · n) time.
For the grid above, here is what each search marks (T means reached):
pacific atlantic
TTTTT ....T
TTTTT ...TT
TTT.. ..TTT
TT... TTTTT
T.... TTTTT
The cells marked in both pictures are the seven cells of the answer.
Step by step
- Store the size.
rowsisheights.len(), andcolsisheights[0].len(), since every row has the same length. - Search from the Pacific with
Self::reach(&heights, 0, 0). The helper takes an edge row and an edge column and returns a grid of booleans marking every cell whose water can flow to that row or that column. The Pacific touches row 0 and column 0. - Search from the Atlantic with
Self::reach(&heights, rows - 1, cols - 1), the last row and the last column. One helper serves both oceans. - Create
resultas an emptyVec<Vec<i32>>. - Loop over rows, then columns, with
rin0..rowsandcin0..cols. This order is the reading order the answer needs. - Keep a cell when
pacific[r][c]andatlantic[r][c]are both true, by pushingvec![r as i32, c as i32]. - Return
resultwithout a semicolon. - Write
reachwithheights: &Vec<Vec<i32>>,edge_row: usizeandedge_col: usize, returning aVec<Vec<bool>>. The&borrows the grid, sopacific_atlanticcan pass it twice. - Create
seenwithvec![vec![false; cols]; rows]. The macro clones the inner vector for every row, so each row is its own vector. - Create the queue as a
VecDeque<(usize, usize)>of cells, each a row and column tuple. - Seed the search. Loop over every cell, and for each one with
r == edge_row || c == edge_col, mark it inseenand push(r, c). These cells touch the ocean, so their water flows straight into it. A cell is marked when it joins the queue, never later, so no cell joins twice. - Create
directionsas a[(i32, i32); 4]with the moves up, down, left and right. They arei32because a move can be negative, while indexes areusize. - Loop with
while let Some((row, col)) = queue.pop_front()until the queue is empty, and loop over the moves withfor &(dr, dc) in &directions. - Compute the neighbor as
i32values:next_row = row as i32 + drandnext_col = col as i32 + dc. - Skip off-grid neighbors by checking that both are at least 0 and below
rows as i32orcols as i32. - Turn them back into
usizeby shadowing both names in oneletwith a tuple. The check above makes the cast safe. - Climb when allowed: if the neighbor isn't seen and
heights[next_row][next_col] >= heights[row][col], mark it and push it. - Return
seen. A true entry marks a cell whose water can reach this ocean.
The solution in Rust
use std::collections::VecDeque;
impl Solution {
fn pacific_atlantic(heights: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let rows = heights.len();
let cols = heights[0].len();
let pacific = Self::reach(&heights, 0, 0);
let atlantic = Self::reach(&heights, rows - 1, cols - 1);
let mut result: Vec<Vec<i32>> = Vec::new();
for r in 0..rows {
for c in 0..cols {
if pacific[r][c] && atlantic[r][c] {
result.push(vec![r as i32, c as i32]);
}
}
}
result
}
fn reach(heights: &Vec<Vec<i32>>, edge_row: usize, edge_col: usize) -> Vec<Vec<bool>> {
let rows = heights.len();
let cols = heights[0].len();
let mut seen = vec![vec![false; cols]; rows];
let mut queue: VecDeque<(usize, usize)> = VecDeque::new();
for r in 0..rows {
for c in 0..cols {
if r == edge_row || c == edge_col {
seen[r][c] = true;
queue.push_back((r, c));
}
}
}
let directions: [(i32, i32); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];
while let Some((row, col)) = queue.pop_front() {
for &(dr, dc) in &directions {
let next_row = row as i32 + dr;
let next_col = col as i32 + dc;
if next_row >= 0 && next_row < rows as i32 && next_col >= 0 && next_col < cols as i32 {
let (next_row, next_col) = (next_row as usize, next_col as usize);
if !seen[next_row][next_col] && heights[next_row][next_col] >= heights[row][col] {
seen[next_row][next_col] = true;
queue.push_back((next_row, next_col));
}
}
}
}
seen
}
}
The Rust details worth a closer look:
- Signed moves, unsigned indexes. Row and column indexes are
usize, which can't be negative. Computingrow - 1at row 0 would underflow: a panic in a debug build and a wrap to a huge number in an optimized build. So the neighbor is computed ini32, range-checked, and only then converted withas usize. - Shadowing.
let (next_row, next_col) = (next_row as usize, next_col as usize);declares new variables with the same names. The oldi32values are no longer reachable, so the later indexing can't use them by mistake. for &(dr, dc) in &directions. Looping over&directionsgives references to the tuples. The pattern&(dr, dc)copies the two numbers out.- Destructuring in
while let.pop_front()returns anOption<(usize, usize)>. The patternSome((row, col))takes the tuple apart, and the loop ends atNone. &Vec<Vec<i32>>. The helper only reads the grid, so it borrows it. Rust code more often takes&[Vec<i32>]for this, but the lesson's signature works the same here.vec![vec![false; cols]; rows]. The macro clones its first argument into every place, which works becauseVec<bool>isClone. Each row is a separate vector, so setting one cell doesn't change another row.
Complexity
Time: O(m · n). Each search marks a cell once, when it joins the queue, so each cell leaves the queue at most once. Each one looks at four neighbors, which is constant work. The two searches and the final loop each take O(m · n).
Space: O(m · n). Each search has a seen grid and a queue of at most m · n cells. The two grids pacific and atlantic are alive together. The answer can hold every cell in the worst case.
Edge cases and common mistakes
- Using
>instead of>=. Water flows between cells of equal height, so the climb must allow equal heights. With>, the ring of 5s in the third example would stop at the corners and miss cells. - Climbing the wrong way. The search walks against the flow, to neighbors that are at least as high. Moving to lower neighbors would answer a different question.
- A single cell. For
[[1]]the edge row and column are both 0 for both oceans, so the one cell is marked by both searches. - One row or one column. For
[[1, 2, 3]]every cell is on the top edge, so the Pacific reaches all of them, and the Atlantic touches the last column and the bottom row, which is the same row. The answer is all three cells. For[[3], [2], [1]]it is all three cells too. - Corners. The top-right and bottom-left cells touch both oceans. They are seeded in both searches, so they always appear in the answer.
- Marking late. Marking a cell when it leaves the queue, instead of when it joins, lets a cell be queued several times.
- Result order. The final loop goes row by row, so the output is in reading order without sorting.
- Lakes. A cell lower than all its neighbors, like the middle 1 in the third example, is never marked. The search moves only to cells at least as high as the current one, and every neighbor of the 1 is higher than it, so the search can't step down into it.
Testing
- The 5-by-5 grid above gives
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]. [[1]]gives[[0, 0]].[[5, 5, 5], [5, 1, 5], [5, 5, 5]]gives[[0, 0], [0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1], [2, 2]].[[1, 2, 3]]gives[[0, 0], [0, 1], [0, 2]].[[3], [2], [1]]gives[[0, 0], [1, 0], [2, 0]].[[2, 1], [1, 2]]gives[[0, 0], [0, 1], [1, 0], [1, 1]].
