Pacific Atlantic Water Flow
To solve this problem, we need to find the cells from which water can flow to both the Pacific and Atlantic oceans. We will perform two DepthFirst Search (DFS) traversals: one starting from the cells touching the Pacific Ocean (top and left edges) and the other starting from the cells touching the Atlantic Ocean (right and bottom edges).
Here’s the stepbystep process:
 Create two boolean matrices
pacific
andatlantic
of size m x n to keep track of the cells that can reach the Pacific and Atlantic oceans respectively.  Run a DFS from the top and left edges to fill the
pacific
matrix, marking the reachable cells as True.  Run a DFS from the right and bottom edges to fill the
atlantic
matrix, marking the reachable cells as True.  Iterate through both matrices to find the cells that can reach both oceans (cells with True in both matrices) and return their coordinates.
Below is the code:


This code will return the required 2D list of grid coordinates where water can flow to both the Pacific and Atlantic oceans, as per the given problem statement.
Define the Interface Input: matrix (coordinates consisting of integer) Output: grid of coordinates
Identify the Invariants
 mxn
 position of the pacific and atlantic ocean
Identify the constraints
 Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.
Search the Problem Space
 grid
Classify the Problem
 Grid Traversal
Analyze the Examples We can represent the flow of water as a graph with nodes representing the unit cell Rules for the flow of water can be applied to each cell to figure out the directionality of the edges Edges can be unidirectional or bidirectional
Converting the grid coordinates to a graph consisting of nodes Figure out the directionality of the edges Apply the rules for the water flow We have to check each node in the graph, whether it has a path to P and A. If it does, then we need to add the coordinate to the result array of array
Do we need a graph data structure to solve this problem?
Solve the Problem by Hand We created the graph We represented the coordinates on the diagram Overlay the coordinates and check the path exists or not
Describe the Pattern
 We don’t care whether it is shortest/longest path
 If it has at least one path to P and A
 The first row and first column is connected to P
 The last row and last column is connected to A
 Any nodes that is not in the first row, first column last row or last column, we need to check if it can reach any node in the first row or first column (P) AND reach any node in the last row or last column (A)
 Traverse the grid, we have to check every node
Brute Force Approach
DFS
Base Case
 If the node is in the first row or first column it can reach P and If the node is in the last row or last column it can reach A
 The node in the last row and first column can reach A & P
 The node in the first row and last column can reach A & P.
 Add the coordinates of those nodes to the result
Recursive Cases
 Non trivial case where we need traverse the graph (one distance away from A) (0, 3) (row, col) (0, n1)  Check if the node height is greater or equal to the node height in (0, n) We can add that cell also to the result
Do we need to keep track of the nodes visited? We can cache the result of whether it is possible to reach either A or P from that cell.
Out of bounds checking to make sure we are within the grid when traversing right, left, up, down directions = {(0,1), (0, 1), (1,0), (1, 0)}
Initialize to false for visited[row][col] The dimension of the visited grid will be the same dimension as the original grid (mxnm)
Unit of Work
 Each node can go up, down, left, right
 Parent needs to tell which node to process
 Which nodes have we already visited and can we reach P & A from this node?
Problem Decomposition
 We can divide the problems into two smaller problems Reach P Reach A We can handle the simpler problems and have a compound condition to check whether a given node can reach both A & P
dfs(matrix, visited, )
Analyze Time and Space Complexity
Outline the Solution

