algoadvance

Leetcode 417. Pacific Atlantic Water Flow

Problem Statement

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges. Each cell will have water flowing to both its four adjacent cells (north, south, east, west) and/or directly into an ocean. Water can only flow in one direction: from a cell to another one with height equal or lower.

The task is to return the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Example:

  1. Input: matrix = 
    [[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]]
  2. Output: 
    [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Constraints:

Clarifying Questions

  1. Flow Clarification: Water flows to adjacent cells with equal or lower height only?
    • Answer: Yes, water can only flow to adjacent cells that have an equal or lower height.
  2. Edge Clarification: Does the water that touches the Pacific or Atlantic by flowing from the edges still start from each cell within the matrix?
    • Answer: Yes, the water can flow from each cell and needs to be checked if it can flow to either ocean by considering all possible routes.
  3. Output Format: Should the coordinates be sorted or in any specific format?
    • Answer: No specific format but providing the list of coordinates in any order is fine.

Strategy

  1. Initial Setup:
    • Define two boolean matrices pacific and atlantic of the same size as the input matrix to keep track of cells that can flow to the respective oceans.
  2. DFS Approach:
    • Use Depth-First Search (DFS) starting from the edges:
      • For the Pacific Ocean, start from cells on the top and left edges.
      • For the Atlantic Ocean, start from cells on the bottom and right edges.
    • From each cell, perform DFS to mark all reachable cells maintaining the height condition.
  3. Result Compilation:
    • Iterate over each cell in the matrix, and if a cell is reachable from both ocean matrices (pacific and atlantic), add it to the result list.

Code

Here is the Java code to solve the problem:

import java.util.ArrayList;
import java.util.List;

public class PacificAtlanticWaterFlow {
    private int[][] directions = // use example from above
    
    public List<int[]> pacificAtlantic(int[][] matrix) {
        List<int[]> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return result;
        }

        int m = matrix.length;
        int n = matrix[0].length;

        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            dfs(matrix, pacific, i, 0, Integer.MIN_VALUE);
            dfs(matrix, atlantic, i, n - 1, Integer.MIN_VALUE);
        }

        for (int j = 0; j < n; j++) {
            dfs(matrix, pacific, 0, j, Integer.MIN_VALUE);
            dfs(matrix, atlantic, m - 1, j, Integer.MIN_VALUE);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.add(new int[]{i, j});
                }
            }
        }

        return result;
    }

    private void dfs(int[][] matrix, boolean[][] visited, int i, int j, int prevHeight) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || matrix[i][j] < prevHeight) {
            return;
        }

        visited[i][j] = true;

        for (int[] dir : directions) {
            dfs(matrix, visited, i + dir[0], j + dir[1], matrix[i][j]);
        }
    }
}

Time Complexity

This efficient solution ensures we cover all possible flows in the matrix while maintaining only necessary data.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI