grid47 Exploring patterns and algorithms
Sep 26, 2024
9 min read
Solution to LeetCode 417: Pacific Atlantic Water Flow Problem
You are given an m x n grid representing an island, where each cell contains an integer representing the height above sea level. The island borders both the Pacific and Atlantic Oceans. The Pacific Ocean touches the left and top edges of the grid, and the Atlantic Ocean touches the right and bottom edges. Water can flow from one cell to an adjacent cell if the adjacent cell’s height is less than or equal to the current cell’s height. The task is to find all the cells where water can flow to both oceans.
Problem
Approach
Steps
Complexity
Input: The input is a 2D integer grid representing the heights of the island cells.
Output: Return a list of coordinates that represent the cells where water can flow to both the Pacific and Atlantic Oceans.
Example: Output: [[0,2],[1,1],[2,0]]
Constraints:
• The output should be a list of valid cell coordinates.
Goal: The goal is to identify all the cells where water can flow to both oceans.
Steps:
• Use depth-first search (DFS) to explore cells from the borders of both oceans.
• Mark cells that can reach the Pacific Ocean from the top and left borders.
• Mark cells that can reach the Atlantic Ocean from the bottom and right borders.
• Return cells that can reach both oceans.
Goal: The problem's constraints ensure that the grid is not too large to process efficiently with DFS.
Steps:
• The grid can have a size of up to 200x200.
• Heights are non-negative integers less than or equal to 100,000.
Assumptions:
• The grid represents a valid island structure.
• Water can flow to any neighboring cell that is lower or equal in height.
• Input: Example 1: Input: heights = [[3,4,5],[6,7,8],[1,2,3]]
• Explanation: In this example, the cells that can flow to both the Pacific and Atlantic oceans are (0,2), (1,1), and (2,0). Water flows from these cells to both oceans as demonstrated in the DFS exploration.
Approach: To solve this problem, we use DFS to explore the cells that can reach the Pacific and Atlantic Oceans, marking them as we go.
Observations:
• The problem asks to find all cells that can reach both oceans.
• We can perform DFS starting from the borders of the grid where water can reach the ocean.
• By marking the cells reachable from the Pacific and Atlantic Oceans separately, we can identify cells that are reachable from both.
Steps:
• Perform DFS for the Pacific Ocean from the top and left borders.
• Perform DFS for the Atlantic Ocean from the bottom and right borders.
• For each cell, check if it is marked in both the Pacific and Atlantic reachable grids, and add it to the result list.
Empty Inputs:
• If the grid has no rows or columns, the result should be an empty list.
Large Inputs:
• Ensure that the solution can handle grids with the maximum size efficiently.
Special Values:
• All cells have the same height: In this case, all cells can reach both oceans.
Constraints:
• The solution should efficiently handle the maximum constraints of 200x200 grid size.
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int m = heights.size(), n = heights[0].size();
vector<vector<bool>> pac(m, vector<bool>(n, false));
vector<vector<bool>> atl(m, vector<bool>(n, false));
for(int j =0; j < n; j++) {
dfs(heights, pac, 0, j);
dfs(heights, atl, m -1, j);
}
for(int j =0; j < m; j++) {
dfs(heights, pac, j, 0);
dfs(heights, atl, j, n -1);
}
vector<vector<int>> ans;
for(int i =0; i < m; i++)
for(int j =0; j < n; j++)
if(pac[i][j] && atl[i][j])
ans.push_back({i, j});
return ans;
}
voiddfs(vector<vector<int>>& h, vector<vector<bool>>&vis, int i, int j) {
vis[i][j] =true;
if(i >0&&!vis[i -1][j] && h[i -1][j] >= h[i][j])
dfs(h, vis, i -1, j);
if(j >0&&!vis[i][j -1] && h[i][j -1] >= h[i][j])
dfs(h, vis, i, j -1);
if(i < h.size() -1&&!vis[i +1][j] && h[i +1][j] >= h[i][j])
dfs(h, vis, i +1, j);
if(j < h[0].size() -1&&!vis[i][j +1] && h[i][j +1] >= h[i][j])
dfs(h, vis, i, j +1);
}
This line declares the `pacificAtlantic` function, which takes a 2D vector representing the elevation map and returns a 2D vector with the coordinates that can reach both oceans.
2 : Variable Initialization
int m = heights.size(), n = heights[0].size();
Here, we initialize variables `m` and `n` to represent the number of rows and columns in the heights matrix.
