Blind 75.29 - Pacific Atlantic Water Flow

Pacific atlantic water flow.

Problem description

Taken directly from LeetCode.

(use html to markdown converter: https://codebeautify.org/html-to-markdown)

Solution type

Caching.

Solution

What a weird question - where does the Alantic end and the Pacific start? Regardless…

I think you have to do a full DFS / BFS on every cell in the grid. Well you don’t “have to” - there’s some caching optimizations you can do - but I think you can construct an adversarial example where every cell needs a DFS / BFS to correctly get reachability on both the Atlantic and Pacific oceans. I do think it’s going to be easier to implement (slightly less efficient but oh well) to DFS / BFS twice, once for Atlantic reachability and once for Pacific reachability.

Okay, this doesn’t work - it times out on a large test case. A full DFS / BFS on each tile is too slow. Note the additional visited tracker, which is necessary to avoid infinite looping on two adjacent tiles with the same height.

def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
    reachability = [[[False, False] for _ in range(len(heights[0]))] for _ in range(len(heights))]
    dfs = []
    for i in range(0, len(heights)):
        for j in range(0, len(heights[0])):
            dfs.append((i, j))
            visited = [(i, j)]
            while len(dfs):
                currentX, currentY = dfs[-1][0], dfs[-1][1] 
                visited.append((currentX, currentY))
                dfs.pop(-1)
                currentHeight = heights[currentX][currentY]
                if currentX == 0 or currentY == 0:
                    reachability[i][j][0] = True
                if currentX == len(heights) - 1 or currentY == len(heights[0]) - 1:
                    reachability[i][j][1] = True
                
                if currentX > 0 and (currentX - 1, currentY) not in visited and heights[currentX - 1][currentY] <= heights[currentX][currentY]:
                    dfs.append((currentX - 1, currentY))
                if currentX < len(heights) - 1 and (currentX + 1, currentY) not in visited and heights[currentX + 1][currentY] <= heights[currentX][currentY]:
                    dfs.append((currentX + 1, currentY))
                if currentY > 0 and (currentX, currentY - 1) not in visited and heights[currentX][currentY - 1] <= heights[currentX][currentY]:
                    dfs.append((currentX, currentY - 1))
                if currentY < len(heights[0]) - 1 and (currentX, currentY + 1) not in visited and heights[currentX][currentY + 1] <= heights[currentX][currentY]:
                    dfs.append((currentX, currentY + 1))
    result = []
    for i in range(0, len(reachability)):
        for j in range(0, len(reachability[0])):
            if reachability[i][j][0] and reachability[i][j][1]:
                result.append([i, j])
    return result

Adding an early break statement makes this solution pass, but this only beats 6% of submissions. So my guess is that there is a more efficient way for me to - probably an approach that uses some additional memory (without changing the asymptotic complexity). What you can probably do is something more akin to what I was thinking at first - mark all border cells as reachable to the Atlantic / Pacific, then DFS on each inner cell, but don’t add cells that can reach both oceans to the DFS. I still feel like this is a minor optimization and won’t actually decrease the asymptotic complexity?. In any case, what I did was the simpler implementation, and that was my main motivation for choosing it.

def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
    reachability = [[[False, False] for _ in range(len(heights[0]))] for _ in range(len(heights))]
    for i in range(0, len(heights)):
        for j in range(0, len(heights[0])):
            dfs = [(i, j)]
            visited = [(i, j)]
            while len(dfs):
                currentX, currentY = dfs[-1][0], dfs[-1][1] 
                visited.append((currentX, currentY))
                dfs.pop(-1)
                currentHeight = heights[currentX][currentY]
                if currentX == 0 or currentY == 0:
                    reachability[i][j][0] = True
                if currentX == len(heights) - 1 or currentY == len(heights[0]) - 1:
                    reachability[i][j][1] = True
                if reachability[i][j][0] and reachability[i][j][1]:
                    break
                
                if currentX > 0 and (currentX - 1, currentY) not in visited and heights[currentX - 1][currentY] <= heights[currentX][currentY]:
                    dfs.append((currentX - 1, currentY))
                if currentX < len(heights) - 1 and (currentX + 1, currentY) not in visited and heights[currentX + 1][currentY] <= heights[currentX][currentY]:
                    dfs.append((currentX + 1, currentY))
                if currentY > 0 and (currentX, currentY - 1) not in visited and heights[currentX][currentY - 1] <= heights[currentX][currentY]:
                    dfs.append((currentX, currentY - 1))
                if currentY < len(heights[0]) - 1 and (currentX, currentY + 1) not in visited and heights[currentX][currentY + 1] <= heights[currentX][currentY]:
                    dfs.append((currentX, currentY + 1))
    result = []
    for i in range(0, len(reachability)):
        for j in range(0, len(reachability[0])):
            if reachability[i][j][0] and reachability[i][j][1]:
                result.append([i, j])
    return result

Doing some analysis: this is an \(O((nm)^2)\) algorithm because for \(nm\) cells, we examine up to \(nm\) cells and do \(O(1)\) work for each of those other cells. It definitely feels like this could be better somehow.

Aha! What a clever way to approach it! So the efficient solution is \(O(n + m)(nm)\); instead of going down from tall heights, you can flip the problem statement around and go up from the borders! That is, flip your height comparisons so that you are adding taller cells to the DFS and only perform DFS on the border cells, i.e. the cells that you know for sure can reach the ocean. This reduces it to \(O((m + n)(mn))\) which is a much nicer time complexity.

I don’t feel like doing all the work to reimplement with the correct solution, so I’ll just show another user’s Java solution below. View it on leetcode here.

public void dfs(int i,int j,int n,int m,int heights[][],int preHeight,boolean vis[][]){
    if(i<0 || j<0 || i==n || j==m || vis[i][j] || preHeight>heights[i][j]) return;
    vis[i][j]=true;
    dfs(i+1,j,n,m,heights, heights[i][j],vis);
    dfs(i,j+1,n,m,heights, heights[i][j],vis);
    dfs(i-1,j,n,m,heights, heights[i][j],vis);
    dfs(i,j-1,n,m,heights, heights[i][j],vis);
}
public List<List<Integer>> pacificAtlantic(int[][] heights) {
    int n=heights.length, m=heights[0].length;
    boolean[][] pacific=new boolean[n][m],atlantic=new boolean[n][m];
    for(int i=0;i<n;i++){
    dfs(i,0,n,m,heights, heights[i][0],pacific); //1st col
    dfs(i,m-1,n,m,heights, heights[i][m-1],atlantic); //last col
    }
    for(int j=0;j<m;j++){
    dfs(0,j,n,m,heights, heights[0][j],pacific); //1st row
    dfs(n-1,j,n,m,heights, heights[n-1][j],atlantic); //last row
    }
    List<List<Integer>> ans=new ArrayList<>();
    for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        if(pacific[i][j] && atlantic[i][j]) ans.add(Arrays.asList(i,j));
    }
    }
    return ans;
}

It is a bit of an ugly problem, honestly - so much code and so many conditionals. I think it’s worth keeping that in mind because this is probably characteristic of any kind of “grid” problem where you have to apply a graph algorithm.