417. Pacific Atlantic Water Flow
Problem Description
You're given an m x n
matrix representing an island where each cell contains a height value. The island is surrounded by two oceans:
- Pacific Ocean: touches the left and top edges of the island
- Atlantic Ocean: touches the right and bottom edges of the island
When it rains on the island, water flows from each cell to neighboring cells (north, south, east, west) if the neighboring cell's height is less than or equal to the current cell's height. Water that reaches cells adjacent to an ocean flows into that ocean.
Your task is to find all cells from which rainwater can flow to both the Pacific Ocean AND the Atlantic Ocean. Return these cells as a list of coordinates [r, c]
.
Key Points:
- Water flows from higher or equal height to lower or equal height cells
- Water can move in 4 directions: up, down, left, right
- A cell must be able to reach both oceans (not just one) to be included in the result
- Cells on the edges are directly adjacent to their respective oceans
Example visualization: If we have a 5ร5 island, the Pacific Ocean borders are at row 0 and column 0, while the Atlantic Ocean borders are at row 4 and column 4. Water from a cell in the middle needs to find paths to both ocean boundaries following the height rules.
Flowchart Walkthrough
First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- Yes: The problem involves a grid where each cell can be connected to its neighbors (up, down, left, right). Water flows between cells based on height relationships, creating edges between nodes (cells). This is essentially a graph traversal problem.
Is it a tree?
- No: The grid structure with multiple possible paths and potential cycles (water can flow in circles if heights allow) means this is not a tree structure.
Is the problem related to directed acyclic graphs?
- No: While water flow creates directed edges (from higher/equal to lower/equal heights), the problem isn't about DAG properties like topological ordering. We need to find cells that can reach both oceans.
Is the problem related to shortest paths?
- No: We don't need to find the shortest path to the oceans. We only need to determine if water can reach both oceans from a given cell, regardless of path length.
Does the problem involve connectivity?
- Yes: The core of the problem is about connectivity - determining which cells are connected to both the Pacific and Atlantic oceans through valid water flow paths.
Does the problem have small constraints?
- Yes: The constraints are typically manageable (m ร n grid with reasonable dimensions), allowing for traversal-based approaches.
DFS/backtracking?
- Yes: DFS is perfect for exploring all possible flow paths from ocean boundaries inward, marking all reachable cells.
Conclusion: The flowchart suggests using DFS (Depth-First Search) to solve this problem. The solution uses DFS (implemented as BFS in the provided code) to traverse from ocean boundaries inward, finding all cells reachable from each ocean, then returning the intersection of these two sets.
Intuition
The key insight is to reverse our thinking. Instead of checking if water from each cell can reach both oceans (which would be inefficient), we ask: "Which cells can be reached FROM each ocean?"
Think about it this way: if water can flow from cell A to the ocean, then we can also trace backwards from the ocean to cell A by going uphill or staying at the same level. This reverse approach is much more efficient.
Here's the thought process:
-
Start from the ocean boundaries: We know cells touching the Pacific (top/left edges) can definitely reach the Pacific. Similarly, cells touching the Atlantic (bottom/right edges) can reach the Atlantic.
-
Flow backwards: From these boundary cells, we can "flow uphill" - moving to neighboring cells with heights greater than or equal to the current cell. This simulates the reverse of water flowing downhill.
-
Mark reachable cells: As we traverse from each ocean, we mark all cells that can be reached. This gives us two sets:
- Set 1: All cells that can reach the Pacific Ocean
- Set 2: All cells that can reach the Atlantic Ocean
-
Find the intersection: The answer is simply the cells that appear in both sets - these are the cells from which water can flow to both oceans.
Why is this approach better? Instead of doing a traversal from each of the m ร n
cells to check if they can reach both oceans (which would be O(m ร n ร (m + n))
), we only do two traversals starting from the ocean boundaries. This reduces our complexity significantly.
The beauty of this solution lies in recognizing that water flow is reversible in terms of reachability - if water can flow from A to B (going downhill), then we can trace from B to A (going uphill).
Solution Approach
The implementation uses BFS (Breadth-First Search) to execute our reverse-flow strategy. Here's how the solution works:
1. Initialize Data Structures:
- Two sets
vis1
andvis2
to track cells reachable from Pacific and Atlantic oceans respectively - Two queues
q1
andq2
for BFS traversal from each ocean - Variables
m
andn
store the dimensions of the grid
2. Identify Ocean Boundaries:
for i in range(m):
for j in range(n):
if i == 0 or j == 0: # Pacific Ocean (top and left edges)
vis1.add((i, j))
q1.append((i, j))
if i == m - 1 or j == n - 1: # Atlantic Ocean (bottom and right edges)
vis2.add((i, j))
q2.append((i, j))
- Cells on row 0 or column 0 touch the Pacific Ocean
- Cells on row
m-1
or columnn-1
touch the Atlantic Ocean - These boundary cells are added to their respective queues and marked as visited
3. BFS Traversal Function:
def bfs(q, vis):
while q:
for _ in range(len(q)):
i, j = q.popleft()
for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]: # 4 directions
x, y = i + a, j + b
if (0 <= x < m and 0 <= y < n and
(x, y) not in vis and
heights[x][y] >= heights[i][j]): # Can flow "uphill"
vis.add((x, y))
q.append((x, y))
- For each cell in the queue, check all 4 neighboring cells
- The key condition:
heights[x][y] >= heights[i][j]
- we can move to cells with equal or greater height (reverse flow) - If a valid unvisited cell is found, mark it as visited and add to queue
4. Execute BFS from Both Oceans:
bfs(q1, vis1) # Find all cells reachable from Pacific bfs(q2, vis2) # Find all cells reachable from Atlantic
5. Find Intersection:
return [(i, j) for i in range(m) for j in range(n)
if (i, j) in vis1 and (i, j) in vis2]
- Return cells that exist in both
vis1
andvis2
- These are the cells from which water can flow to both oceans
Time Complexity: O(m ร n)
- Each cell is visited at most twice (once from each ocean)
Space Complexity: O(m ร n)
- For the visited sets and queues in worst case
The algorithm elegantly solves the problem by reversing the flow direction and using set intersection to find cells connected to both oceans.
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small 3ร3 example to illustrate the solution approach:
heights = [[3, 3, 5], [3, 1, 3], [0, 2, 4]]
Step 1: Identify Ocean Boundaries
Pacific Ocean touches:
- Top row: (0,0), (0,1), (0,2)
- Left column: (0,0), (1,0), (2,0)
Atlantic Ocean touches:
- Bottom row: (2,0), (2,1), (2,2)
- Right column: (0,2), (1,2), (2,2)
Initial state:
vis1
(Pacific): {(0,0), (0,1), (0,2), (1,0), (2,0)}vis2
(Atlantic): {(2,0), (2,1), (2,2), (0,2), (1,2)}
Step 2: BFS from Pacific Ocean (reverse flow - going uphill)
Starting from Pacific boundaries, we can reach cells with height โฅ current:
From (0,0) with height 3:
- Check (1,0): height 3 โฅ 3 โ (already in vis1)
- Check (0,1): height 3 โฅ 3 โ (already in vis1)
From (0,1) with height 3:
- Check (1,1): height 1 < 3 โ (can't go there)
From (0,2) with height 5:
- Check (1,2): height 3 < 5 โ (can't go there)
From (1,0) with height 3:
- Check (1,1): height 1 < 3 โ (can't go there)
From (2,0) with height 0:
- Check (2,1): height 2 โฅ 0 โ (add to vis1)
After processing (2,1) with height 2:
- Check (1,1): height 1 < 2 โ (can't go there)
- Check (2,2): height 4 โฅ 2 โ (add to vis1)
Final vis1
: {(0,0), (0,1), (0,2), (1,0), (2,0), (2,1), (2,2)}
Step 3: BFS from Atlantic Ocean (reverse flow - going uphill)
Starting from Atlantic boundaries:
From (2,2) with height 4:
- Check (2,1): height 2 < 4 โ (can't go there)
- Check (1,2): height 3 < 4 โ (can't go there)
From (0,2) with height 5:
- Check (0,1): height 3 < 5 โ (can't go there)
- Check (1,2): height 3 < 5 โ (can't go there)
From (2,0) with height 0:
- Check (1,0): height 3 โฅ 0 โ (add to vis2)
From (1,0) with height 3:
- Check (0,0): height 3 โฅ 3 โ (add to vis2)
From (0,0) with height 3:
- Check (0,1): height 3 โฅ 3 โ (add to vis2)
Final vis2
: {(2,0), (2,1), (2,2), (0,2), (1,2), (1,0), (0,0), (0,1)}
Step 4: Find Intersection
Cells in both vis1 AND vis2:
- (0,0) โ in both
- (0,1) โ in both
- (0,2) โ in both
- (1,0) โ in both
- (2,0) โ in both
- (2,1) โ in both
- (2,2) โ in both
Result: [[0,0], [0,1], [0,2], [1,0], [2,0], [2,1], [2,2]]
These are all the cells from which water can flow to both oceans. Notice that (1,1) with height 1 is surrounded by higher cells, creating a "valley" that prevents water from reaching either ocean, and (1,2) can only reach the Atlantic but not the Pacific.
Solution Implementation
1from collections import deque
2from typing import List
3
4class Solution:
5 def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
6 """
7 Find all cells where water can flow to both Pacific and Atlantic oceans.
8 Water flows from higher or equal height cells to lower or equal height cells.
9 Pacific ocean touches left and top edges, Atlantic ocean touches right and bottom edges.
10 """
11
12 def bfs(queue: deque, visited: set) -> None:
13 """
14 Perform BFS to find all cells that can reach the ocean.
15 Start from ocean edges and move to cells with equal or greater height.
16 """
17 while queue:
18 # Process all cells at current level
19 level_size = len(queue)
20 for _ in range(level_size):
21 curr_row, curr_col = queue.popleft()
22
23 # Check all 4 adjacent cells (up, down, left, right)
24 directions = [[0, -1], [0, 1], [1, 0], [-1, 0]]
25 for delta_row, delta_col in directions:
26 next_row = curr_row + delta_row
27 next_col = curr_col + delta_col
28
29 # Check if next cell is valid and water can flow backwards
30 # (from next cell to current cell, which means next >= current)
31 if (0 <= next_row < rows and
32 0 <= next_col < cols and
33 (next_row, next_col) not in visited and
34 heights[next_row][next_col] >= heights[curr_row][curr_col]):
35
36 visited.add((next_row, next_col))
37 queue.append((next_row, next_col))
38
39 # Get grid dimensions
40 rows = len(heights)
41 cols = len(heights[0])
42
43 # Initialize visited sets and queues for both oceans
44 pacific_visited = set()
45 atlantic_visited = set()
46 pacific_queue = deque()
47 atlantic_queue = deque()
48
49 # Add border cells to respective ocean queues
50 for row in range(rows):
51 for col in range(cols):
52 # Pacific ocean: top edge (row=0) or left edge (col=0)
53 if row == 0 or col == 0:
54 pacific_visited.add((row, col))
55 pacific_queue.append((row, col))
56
57 # Atlantic ocean: bottom edge (row=rows-1) or right edge (col=cols-1)
58 if row == rows - 1 or col == cols - 1:
59 atlantic_visited.add((row, col))
60 atlantic_queue.append((row, col))
61
62 # Find all cells reachable from each ocean
63 bfs(pacific_queue, pacific_visited)
64 bfs(atlantic_queue, atlantic_visited)
65
66 # Return cells that can reach both oceans (intersection of both sets)
67 result = []
68 for row in range(rows):
69 for col in range(cols):
70 if (row, col) in pacific_visited and (row, col) in atlantic_visited:
71 result.append([row, col])
72
73 return result
74
1class Solution {
2 // Global variables to store the grid and its dimensions
3 private int[][] heights;
4 private int rows;
5 private int cols;
6
7 public List<List<Integer>> pacificAtlantic(int[][] heights) {
8 // Initialize dimensions
9 rows = heights.length;
10 cols = heights[0].length;
11 this.heights = heights;
12
13 // Queues for BFS from Pacific and Atlantic oceans
14 Deque<int[]> pacificQueue = new LinkedList<>();
15 Deque<int[]> atlanticQueue = new LinkedList<>();
16
17 // Sets to track visited cells (encoded as row * cols + col)
18 Set<Integer> pacificVisited = new HashSet<>();
19 Set<Integer> atlanticVisited = new HashSet<>();
20
21 // Initialize starting points for both oceans
22 for (int row = 0; row < rows; row++) {
23 for (int col = 0; col < cols; col++) {
24 // Pacific Ocean: cells on top edge or left edge
25 if (row == 0 || col == 0) {
26 int encodedPosition = row * cols + col;
27 pacificVisited.add(encodedPosition);
28 pacificQueue.offer(new int[] {row, col});
29 }
30 // Atlantic Ocean: cells on bottom edge or right edge
31 if (row == rows - 1 || col == cols - 1) {
32 int encodedPosition = row * cols + col;
33 atlanticVisited.add(encodedPosition);
34 atlanticQueue.offer(new int[] {row, col});
35 }
36 }
37 }
38
39 // Perform BFS from both oceans to find reachable cells
40 bfs(pacificQueue, pacificVisited);
41 bfs(atlanticQueue, atlanticVisited);
42
43 // Find cells that can reach both oceans
44 List<List<Integer>> result = new ArrayList<>();
45 for (int row = 0; row < rows; row++) {
46 for (int col = 0; col < cols; col++) {
47 int encodedPosition = row * cols + col;
48 // If cell is reachable from both oceans, add to result
49 if (pacificVisited.contains(encodedPosition) &&
50 atlanticVisited.contains(encodedPosition)) {
51 result.add(Arrays.asList(row, col));
52 }
53 }
54 }
55
56 return result;
57 }
58
59 private void bfs(Deque<int[]> queue, Set<Integer> visited) {
60 // Direction vectors for moving up, right, down, left
61 int[] directions = {-1, 0, 1, 0, -1};
62
63 while (!queue.isEmpty()) {
64 // Process all cells at current level
65 int levelSize = queue.size();
66 for (int i = 0; i < levelSize; i++) {
67 int[] currentCell = queue.poll();
68 int currentRow = currentCell[0];
69 int currentCol = currentCell[1];
70
71 // Explore all 4 directions
72 for (int dir = 0; dir < 4; dir++) {
73 int nextRow = currentRow + directions[dir];
74 int nextCol = currentCol + directions[dir + 1];
75 int encodedNextPosition = nextRow * cols + nextCol;
76
77 // Check if next cell is valid and water can flow from it to current cell
78 if (nextRow >= 0 && nextRow < rows &&
79 nextCol >= 0 && nextCol < cols &&
80 !visited.contains(encodedNextPosition) &&
81 heights[nextRow][nextCol] >= heights[currentRow][currentCol]) {
82
83 // Mark as visited and add to queue for further exploration
84 visited.add(encodedNextPosition);
85 queue.offer(new int[] {nextRow, nextCol});
86 }
87 }
88 }
89 }
90 }
91}
92
1typedef pair<int, int> pii;
2
3class Solution {
4public:
5 vector<vector<int>> heightsGrid;
6 int rows;
7 int cols;
8
9 vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
10 // Initialize dimensions and store the heights grid
11 rows = heights.size();
12 cols = heights[0].size();
13 this->heightsGrid = heights;
14
15 // Queues for BFS from Pacific and Atlantic oceans
16 queue<pii> pacificQueue;
17 queue<pii> atlanticQueue;
18
19 // Sets to track visited cells for each ocean (using flattened indices)
20 unordered_set<int> pacificVisited;
21 unordered_set<int> atlanticVisited;
22
23 // Initialize starting points for both oceans
24 for (int row = 0; row < rows; ++row) {
25 for (int col = 0; col < cols; ++col) {
26 // Pacific Ocean: top row and left column
27 if (row == 0 || col == 0) {
28 int flatIndex = row * cols + col;
29 pacificVisited.insert(flatIndex);
30 pacificQueue.emplace(row, col);
31 }
32 // Atlantic Ocean: bottom row and right column
33 if (row == rows - 1 || col == cols - 1) {
34 int flatIndex = row * cols + col;
35 atlanticVisited.insert(flatIndex);
36 atlanticQueue.emplace(row, col);
37 }
38 }
39 }
40
41 // Perform BFS from both oceans to find all reachable cells
42 bfs(pacificQueue, pacificVisited);
43 bfs(atlanticQueue, atlanticVisited);
44
45 // Find cells that can reach both oceans
46 vector<vector<int>> result;
47 for (int row = 0; row < rows; ++row) {
48 for (int col = 0; col < cols; ++col) {
49 int flatIndex = row * cols + col;
50 // If cell is reachable from both oceans, add to result
51 if (pacificVisited.count(flatIndex) && atlanticVisited.count(flatIndex)) {
52 result.push_back({row, col});
53 }
54 }
55 }
56
57 return result;
58 }
59
60 void bfs(queue<pii>& bfsQueue, unordered_set<int>& visited) {
61 // Direction vectors for up, right, down, left movement
62 vector<int> directions = {-1, 0, 1, 0, -1};
63
64 while (!bfsQueue.empty()) {
65 // Process all cells at current BFS level
66 int levelSize = bfsQueue.size();
67 for (int i = 0; i < levelSize; ++i) {
68 auto currentCell = bfsQueue.front();
69 bfsQueue.pop();
70
71 // Check all 4 adjacent cells
72 for (int dir = 0; dir < 4; ++dir) {
73 int nextRow = currentCell.first + directions[dir];
74 int nextCol = currentCell.second + directions[dir + 1];
75 int flatIndex = nextRow * cols + nextCol;
76
77 // Check if next cell is valid, unvisited, and water can flow from it to current cell
78 if (nextRow >= 0 && nextRow < rows &&
79 nextCol >= 0 && nextCol < cols &&
80 !visited.count(flatIndex) &&
81 heightsGrid[nextRow][nextCol] >= heightsGrid[currentCell.first][currentCell.second]) {
82
83 visited.insert(flatIndex);
84 bfsQueue.emplace(nextRow, nextCol);
85 }
86 }
87 }
88 }
89 }
90};
91
1/**
2 * Find all cells where water can flow to both Pacific and Atlantic oceans
3 * Water flows from higher or equal height cells to lower or equal height cells
4 * Pacific ocean touches left and top edges, Atlantic ocean touches right and bottom edges
5 */
6function pacificAtlantic(heights: number[][]): number[][] {
7 const rows = heights.length;
8 const cols = heights[0].length;
9
10 // Direction vectors for up, right, down, left
11 const directions: number[][] = [
12 [1, 0], // down
13 [0, 1], // right
14 [-1, 0], // up
15 [0, -1], // left
16 ];
17
18 // Track how many oceans each cell can reach (0, 1, or 2)
19 const reachableCount: number[][] = new Array(rows)
20 .fill(0)
21 .map(() => new Array(cols).fill(0));
22
23 // Track visited cells during DFS traversal
24 const visited: boolean[][] = new Array(rows)
25 .fill(0)
26 .map(() => new Array(cols).fill(false));
27
28 /**
29 * Depth-first search to mark all cells reachable from ocean edges
30 * Water flows backwards from ocean to higher or equal elevation cells
31 */
32 const dfs = (row: number, col: number): void => {
33 // Skip if already visited in current traversal
34 if (visited[row][col]) {
35 return;
36 }
37
38 // Mark cell as reachable from current ocean
39 reachableCount[row][col]++;
40 visited[row][col] = true;
41
42 const currentHeight = heights[row][col];
43
44 // Explore all four directions
45 for (const [deltaRow, deltaCol] of directions) {
46 const nextRow = row + deltaRow;
47 const nextCol = col + deltaCol;
48
49 // Check bounds and if water can flow from next cell to current cell
50 // (heights[nextRow]?.[nextCol] handles boundary checking)
51 if (currentHeight <= (heights[nextRow] ?? [])[nextCol]) {
52 dfs(nextRow, nextCol);
53 }
54 }
55 };
56
57 // Process Pacific Ocean (top edge)
58 for (let col = 0; col < cols; col++) {
59 dfs(0, col);
60 }
61
62 // Process Pacific Ocean (left edge)
63 for (let row = 0; row < rows; row++) {
64 dfs(row, 0);
65 }
66
67 // Reset visited array for Atlantic Ocean traversal
68 visited.forEach(row => row.fill(false));
69
70 // Process Atlantic Ocean (bottom edge)
71 for (let col = 0; col < cols; col++) {
72 dfs(rows - 1, col);
73 }
74
75 // Process Atlantic Ocean (right edge)
76 for (let row = 0; row < rows; row++) {
77 dfs(row, cols - 1);
78 }
79
80 // Collect all cells that can reach both oceans (count = 2)
81 const result: number[][] = [];
82 for (let row = 0; row < rows; row++) {
83 for (let col = 0; col < cols; col++) {
84 if (reachableCount[row][col] === 2) {
85 result.push([row, col]);
86 }
87 }
88 }
89
90 return result;
91}
92
Time and Space Complexity
Time Complexity: O(m * n)
where m
is the number of rows and n
is the number of columns in the heights matrix.
- The initial setup iterates through all cells once to identify border cells:
O(m * n)
- The BFS from Pacific ocean borders visits each reachable cell at most once:
O(m * n)
- The BFS from Atlantic ocean borders visits each reachable cell at most once:
O(m * n)
- The final iteration to find cells in both sets:
O(m * n)
- Total:
O(m * n) + O(m * n) + O(m * n) + O(m * n) = O(m * n)
Space Complexity: O(m * n)
vis1
set can contain at most all cells:O(m * n)
vis2
set can contain at most all cells:O(m * n)
q1
queue can contain at most all cells during BFS:O(m * n)
q2
queue can contain at most all cells during BFS:O(m * n)
- The result list can contain at most all cells:
O(m * n)
- Total:
O(m * n)
(since these are not all used simultaneously at maximum capacity, the overall space complexity remainsO(m * n)
)
Common Pitfalls
1. Incorrect Flow Direction Logic
One of the most common mistakes is misunderstanding the flow direction when implementing the reverse-flow approach. Students often write:
Incorrect:
# Wrong: checking if we can flow "downhill" in reverse traversal if heights[next_row][next_col] <= heights[curr_row][curr_col]: visited.add((next_row, next_col))
Correct:
# Right: we need to go "uphill" when traversing backwards from ocean if heights[next_row][next_col] >= heights[curr_row][curr_col]: visited.add((next_row, next_col))
Why this matters: Since we're traversing backwards from the ocean, we need to move to cells with equal or greater height. Think of it as asking "which cells could have sent water to the current cell?" - only cells with height โฅ current cell's height.
2. Using Lists Instead of Sets for Visited Tracking
Using lists for the visited
data structure severely impacts performance:
Inefficient:
pacific_visited = [] # O(n) lookup time atlantic_visited = [] # Checking membership becomes O(n) if [next_row, next_col] not in pacific_visited: pacific_visited.append([next_row, next_col])
Efficient:
pacific_visited = set() # O(1) lookup time
atlantic_visited = set()
# Checking membership is O(1)
if (next_row, next_col) not in pacific_visited:
pacific_visited.add((next_row, next_col))
3. Forgetting to Handle Equal Heights
A critical oversight is not allowing water to flow between cells of equal height:
Wrong:
# Only allows strictly greater heights if heights[next_row][next_col] > heights[curr_row][curr_col]:
Correct:
# Allows equal or greater heights if heights[next_row][next_col] >= heights[curr_row][curr_col]:
Water can flow horizontally across cells of the same height, which is essential for finding all valid paths.
4. Incorrect Ocean Boundary Identification
Mixing up which edges belong to which ocean:
Common Mistake:
# Wrong assignment of oceans if row == 0 or col == cols - 1: # Mixing top with right edge pacific_visited.add((row, col))
Correct:
# Pacific: top (row=0) and left (col=0) if row == 0 or col == 0: pacific_visited.add((row, col)) # Atlantic: bottom (row=rows-1) and right (col=cols-1) if row == rows - 1 or col == cols - 1: atlantic_visited.add((row, col))
5. Not Processing All Cells at Current BFS Level
Forgetting to process all cells at the current level before moving to the next can lead to incorrect traversal:
Problematic:
while queue: curr_row, curr_col = queue.popleft() # Immediately processing without level separation for delta_row, delta_col in directions: # ...
Better (though both work for this problem):
while queue:
level_size = len(queue)
for _ in range(level_size):
curr_row, curr_col = queue.popleft()
# Process all cells at current distance from ocean
While both approaches find the correct cells, level-by-level processing is clearer and helps if you need to track distance from oceans.
What's the relationship between a tree and a graph?
Recommended Readings
https assets algo monster cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS As the name suggests
https assets algo monster cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell Breadth First Search BFS
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Want a Structured Path to Master System Design Too? Donโt Miss This!