\

Pacific Atlantic Water Flow

Difficulty: N/A | Solved: December 20, 2025

Problem

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell’s height is less than or equal to the current cell’s height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Example 1:

Input: heights = [[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]] Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]] Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below: [0,4]: [0,4] -> Pacific Ocean   [0,4] -> Atlantic Ocean [1,3]: [1,3] -> [0,3] -> Pacific Ocean   [1,3] -> [1,4] -> Atlantic Ocean [1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean   [1,4] -> Atlantic Ocean [2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean   [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean [3,0]: [3,0] -> Pacific Ocean   [3,0] -> [4,0] -> Atlantic Ocean [3,1]: [3,1] -> [3,0] -> Pacific Ocean   [3,1] -> [4,1] -> Atlantic Ocean [4,0]: [4,0] -> Pacific Ocean [4,0] -> Atlantic Ocean Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.

Brainstorming

so for each cell we have to check the possibility of wether the water can travel travel top or left and bottom or right , if both are true then we can add that cell row and column to our results array , it is kind of similar to [[Longest increasing path in matrix]] in this sense .

but how do we check it ? we already have the condition for it . Each cell has a number and we can only move in that direction if the number in our next step is smaller than this. A DFS at each cell can work here but we have to be smart with our conditions

so we need to make sure that we move top left so i think we can just return True or false if we cannot move in either of these direction then we return False for Pacific

same we can do for bottom and right , we can just return True or False if we cannot move in either of these directions then we return for atlantic. If we can do both then we can just add the current cell to our final list

below is code structure

heights = [[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]]

M = len(heights)
N = len(heights[0])

final_list = []

def dfs_helper(r,c,curr_height):
	can_reach_atlantic = False
	can_reach_pacific = False
	# base case for boundaries
	if r < 0 or c < 0 or r >= M or c >= N:
		return False
	# base case for success if we reach atlantic 
	if r == M -1 or c == N -1 :
		return True
	
	# base case for success if we reach pacific
	if r == 0 or c == 0:
		return True
		
	if heights[r][c] <= curr_height:
		can_reach_atlantic = (dfs_helper(r+1,c) or dfs_helper(r,c+1))
		can_reach_pacific = (dfs_helper(r-1,c) or dfs_helper(r,c-1))
	else:
		return False
	
	return can_reach_atlantic and can_reach_pacific
	
for i in range(M):
	for j in range(N):
		can_reach_pacific_and_atlantic = dfs_helper(r,c,heights[i][j]):
			if can_reach_pacific_and_atlantic:
				final_list.append([i,j])
  • 🍅 (pomodoro::WORK) (duration:: 20m) (begin:: 2025-12-19 19:32) - (end:: 2025-12-19 19:52)

Optimal solution

we need to first fix the brute force

heights = [[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]]

M = len(heights)
N = len(heights[0])

final_list = []

def dfs_helper(r,c,prev_height,visited):
	# base case for boundaries
	if r < 0 or c < 0 or r >= M or c >= N:
		return (False,False)

	# base case for height condition failure
	if heights[r][c] > prev_height:
		return (False, False)
	
	visited.update([r,c])
	can_reach_atlantic = False
	can_reach_pacific = False
	
	#  if we reach atlantic 
	if r == M -1 or c == N -1 :
		can_reach_atlantic = True	 
	#  if we reach pacific
	if r == 0 or c == 0:
		can_reach_pacific = True
		
	pacific_res_down, atlantic_res_down = dfs_helper(r, c+1, heights[r][c], visited)
	pacific_res_up , atlantic_res_up = dfs_helper(r, c-1, heights[r][c], visited)
	
	pacific_res_left , atlantic_res_left = dfs_helper(r-1, c, heights[r][c], visited)
		pacific_res_right , atlantic_res_right = dfs_helper(r+1, c, heights[r][c], visited)
	can_reach_atlantic = can_reach_atlantic or atlantic_res_right or atlantic_res_left or atlantic_res_up or atlantic_res_down 
	can_reach_pacific = can_reach_pacific or pacific_res_right or pacific_res_left or pacific_res_up or pacific_res_down 

	visited.remove([r,c])
	return can_reach_atlantic and can_reach_pacific
	
for i in range(M):
	for j in range(N):
		visited = set()
		can_reach_pacific, can_reach_atlantic = dfs_helper(r,c,heights[i][j],visted):
			if can_reach_pacific and can_reach_atlantic:
				final_list.append([i,j])
		

print(final_list)

This is a valiant effort to fix the brute-
force approach. You have correctly identified almost all the complex pieces: returning a tuple, handling prev_height, and needing a visited set.

However, the implementation has some critical bugs that make it very difficult to fix. This is a perfect example of how a seemingly simple brute-force approach can become a “tar pit” of complexity. This is an important lesson in itself!

Let’s quickly point out the issues to see why the “flipped” approach is so much cleaner.

  1. The visited set is broken:

    • visited.update([r,c]): This will add the numbers r and c to the set, not the coordinate tuple (r, c). You would need visited.add((r, c)).

    • The bigger problem: You’re passing the same visited set down to all four recursive calls. The “down” call will add nodes to visited, and then the “up” call will see those nodes as already visited and fail incorrectly. You would need to pass a copy of the visited set to each recursive call, which is very inefficient.

    • visited.remove([r,c]) will also fail because [r,c] is a list, not the tuple (r,c) you would have added.

  2. The Final return:

    • return can_reach_atlantic and can_reach_pacific

    • This still doesn’t work. A call to dfs_helper(r,c) will return True only if that specific subpath can reach both oceans, which is almost never true. You need the final and to be in the main for loop, not the helper. The helper needs to report everything it found. Your return (can_reach_pacific, can_reach_atlantic) was closer.

Let’s stop trying to fix this. The complexity is a clear sign that this is the wrong path. Your initial intuition to separate the problem was right, but this implementation path is a dead end.

Optimal The “Self-Nudge” - Let’s Flip the Problem Upside Down.

Instead of asking, “Can this cell flow out to the oceans?”

Let’s ask the opposite question: “Which cells can the ocean water flow into?”

This approach is vastly simpler to implement correctly.

Recap:

  1. Create a pacific_reachable set.
  2. Start DFS from all cells touching the Pacific to find every cell that can flow to them. Add these to pacific_reachable.
  3. Create an atlantic_reachable set.
  4. Start DFS from all cells touching the Atlantic to find every cell that can flow to them. Add these to atlantic_reachable.
  5. The answer is the intersection of these two sets.

Let’s Design the NEW dfs Helper for this approach.

dfs(r, c, visited_set, prev_height)

  • visited_set: The specific set for the ocean we’re currently exploring (e.g., pacific_reachable).
  • prev_height: The height of the cell we just came from. The rule for flowing “inland” is heights[r][c] >= prev_height.

Logic for dfs(r, c, visited_set, prev_height):

  1. Base Cases (Failure/Stop conditions):

    • Out of bounds? (r < 0, etc.) -> Stop.
    • Current cell already in visited_set? -> Stop (we’ve already processed this path).
    • heights[r][c] < prev_height? -> Can’t flow “uphill” from the ocean. Stop.

  2. If none of the base cases are met, this is a valid cell:

    • “Visit”: Add (r, c) to the visited_set.

    • Explore: Make four recursive calls to neighbors. The new prev_height for these calls will be the height of the current cell, heights[r][c].

      • dfs(r+1, c, visited_set, heights[r][c])
      • dfs(r-1, c, visited_set, heights[r][c])
      • … etc.

There is no return value needed other than None. The function’s only job is to populate the visited_set. There’s also no explicit “undo” because we want the visited_set to be shared for the entire duration of one ocean’s search.

(Prompt):

  1. Write the code for this new, simpler dfs helper.
  2. Write the main for loops that will kick off this dfs for all the Pacific border cells.
heights = [[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]]

M = len(heights) # rows
N = len(heights[0]) # columns

pacific_reachable = set()
atlantic_reachable = set()

final_list = []

# recursive helper

def dfs_helper(r,c,visited,prev_height):
	if r < 0 or c < 0 or r >= M or c >=N:
		return
		
	if (r,c) in visited:
		return
	
	if heights[r][c] < prev_height:
		return
	
	visited.add((r,c))
	
	dfs_helper(r+1,c, visited, heights[r][c])
	dfs_helper(r-1,c, visited, heights[r][c])
	dfs_helper(r,c+1, visited, heights[r][c])
	dfs_helper(r,c-1, visited, heights[r][c])
	
# base cases top row and left column is pacific reachable 

for j in range(N): # top row 
	dfs_helper(0,j,pacific_reachable, heights[0][j])

for i in range(M): # left column
	dfs_helper(i,0,pacific_reachable, heights[i][0])

# base cases for bottom row and right column is atlantic reachable

for j in range(N): # bottom row
	dfs_helper(M-1, j, atlantic_reachable, heights[M-1][j])

for i in range(M): # right column
	dfs_helper(i, N-1, atlantic_reachable, heights[i][N-1])


final_set = pacific_reachable & atlantic_reachable

# final list
for i in final_set:
	final_list.append([i[0], i[1]])
	
print(final_list)
  • 🍅 (pomodoro::WORK) (duration:: 30m) (begin:: 2025-12-19 20:20) - (end:: 2025-12-19 20:50)
  • 🥤 (pomodoro::BREAK) (duration:: 15m) (begin:: 2025-12-19 20:52) - (end:: 2025-12-19 21:07)