Python DFS bests 85%. Tips for all DFS in matrix question.


  • 27
    B

    The DFS solution is straightforward. Starting from each point, and dfs its neighbor if the neighbor is equal or less than itself. And maintain two boolean matrix for two oceans, indicating an ocean can reach to that point or not. Finally go through all nodes again and see if it can be both reached by two oceans. The trick is if a node is already visited, no need to visited again. Otherwise it will reach the recursion limits.

    This question is very similar to https://leetcode.com/problems/longest-increasing-path-in-a-matrix/ And here are some common tips for this kind of question

    1. init a directions var like self.directions = [(1,0),(-1,0),(0,1),(0,-1)] so that when you want to explore from a node, you can just do
    for direction in self.directions:
                x, y = i + direction[0], j + direction[1]
    
    1. this is a what I normally do for a dfs helper method for exploring a matrix
    def dfs(self, i, j, matrix, visited, m, n):
      if visited: 
        # return or return a value
      for dir in self.directions:
        x, y = i + direction[0], j + direction[1]
            if x < 0 or x >= m or y < 0 or y >= n or matrix[x][y] <= matrix[i][j] (or a condition you want to skip this round):
               continue
            # do something like
            visited[i][j] = True
            # explore the next level like
            self.dfs(x, y, matrix, visited, m, n)
    

    Hope it helps

    Solution

    class Solution(object):
        def pacificAtlantic(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: List[List[int]]
            """
            if not matrix: return []
            self.directions = [(1,0),(-1,0),(0,1),(0,-1)]
            m = len(matrix)
            n = len(matrix[0])
            p_visited = [[False for _ in range(n)] for _ in range(m)]
            
            a_visited = [[False for _ in range(n)] for _ in range(m)]
            result = []
            
            for i in range(m):
                # p_visited[i][0] = True
                # a_visited[i][n-1] = True
                self.dfs(matrix, i, 0, p_visited, m, n)
                self.dfs(matrix, i, n-1, a_visited, m, n)
            for j in range(n):
                # p_visited[0][j] = True
                # a_visited[m-1][j] = True
                self.dfs(matrix, 0, j, p_visited, m, n)
                self.dfs(matrix, m-1, j, a_visited, m, n)
                
            for i in range(m):
                for j in range(n):
                    if p_visited[i][j] and a_visited[i][j]:
                        result.append([i,j])
            return result
                    
                    
        def dfs(self, matrix, i, j, visited, m, n):
            # when dfs called, meaning its caller already verified this point 
            visited[i][j] = True
            for dir in self.directions:
                x, y = i + dir[0], j + dir[1]
                if x < 0 or x >= m or y < 0 or y >= n or visited[x][y] or matrix[x][y] < matrix[i][j]:
                    continue
                self.dfs(matrix, x, y, visited, m, n)
    # 113 / 113 test cases passed.
    # Runtime: 196 ms
    

    Solution for longest increasing path in matrix

    class Solution(object):
        def longestIncreasingPath(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: int
            """
            if not matrix: return 0
            self.directions = [(1,0),(-1,0),(0,1),(0,-1)]
            m = len(matrix)
            n = len(matrix[0])
            cache = [[-1 for _ in range(n)] for _ in range(m)]
            res = 0
            for i in range(m):
                for j in range(n):
                    cur_len = self.dfs(i, j, matrix, cache, m, n)
                    res = max(res, cur_len)
            return res
            
        def dfs(self, i, j, matrix, cache, m, n):
            if cache[i][j] != -1:
                return cache[i][j]
            res = 1
            for direction in self.directions:
                x, y = i + direction[0], j + direction[1]
                if x < 0 or x >= m or y < 0 or y >= n or matrix[x][y] <= matrix[i][j]:
                    continue
                length = 1 + self.dfs(x, y, matrix, cache, m, n)
                res = max(length, res)
            cache[i][j] = res
            return res
    

  • 3
    P

    Great instruction. Use bit mask based on your solution.

    class Solution(object):
        def pacificAtlantic(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: List[List[int]]
            """
            if not matrix:
                return matrix
            self.searchPath = [[0,1],[0,-1],[1,0],[-1,0]] 
            m = len(matrix)
            n = len(matrix[0])
            res = [[0 for _ in range(n)] for _ in range(m)] #Mask = 01, Top-left(Pacific), Mask = 10, Bottom-right(Atlantic), res[i][j] = 11
            ans = []
            for i in range(m):
                self.dfs(matrix, res, i,  0, 1)
                self.dfs(matrix, res, i, n-1, 2)
            for i in range(n):
                self.dfs(matrix, res, 0, i, 1)
                self.dfs(matrix, res, m-1, i, 2)
            for i in range(m):
                for j in range(n):
                    if res[i][j] == 3:
                        ans.append([i,j])
            return ans
            
        def dfs(self, matrix, res, i, j, mask):
            res[i][j] = res[i][j]|mask
            for p in self.searchPath:
                x = i + p[0]
                y = j + p[1]
                if x >= 0 and x < len(matrix) and y>=0 and y < len(matrix[0]) and res[x][y]&mask == 0 and matrix[i][j]<=matrix[x][y]:
                    self.dfs(matrix, res, x, y, mask)
    

  • 1

    Another python using complex number to avoid boundary checking:

    moves = [1, -1, 1j, -1j]
    
    def pacificAtlantic(self, matrix):
    	m, n = len(matrix), len(zip(*matrix))
    	def bfs(matrix):
    		maps = {x + y*1j: matrix[x][y] for x in xrange(m) for y in xrange(n)}
    		visited = {x for x in xrange(m)} | {y * 1j for y in xrange(n)}
    		layer = set(visited)
    		while layer:
    			layer = {pos+mov    for pos in layer
    			                    for mov in moves
    						if	pos+mov in maps          and
    							pos+mov not in visited   and
    							maps[pos+mov] >= maps[pos]}
    			visited |= layer 
    		return visited
    	points = bfs(matrix) & {m-1+n*1j-1j-pos for pos in bfs([row[::-1] for row in matrix[::-1]])}
    	return [[p.real, p.imag] for p in points]

  • 0
    L

    How does it make logical sense that at (2,0) in the pacific_visit matrix we have 0? Isn't the pacific/atlantic visit matrixes showing a 1 where water can be pushed from and thus being touched? Wouldn't all the borders technically have a 1 since they are touching a body of water? Maybe I'm not understanding the question clearly and someone can clarify.

    Here's the example that I run where I get that the point (2,0) is 0 in the pacific visited matrix
    Pacific ~ ~ ~ ~ ~
    ~ 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 *
    * * * * * Atlantic


  • 0
    D

    I like to use inner function for dfs because it has access to variable reference declared in the outer function, thus it can have less parameters

    def pacificAtlantic(self, matrix):
        if not matrix or not matrix[0]:
            return []
        
        h, w = len(matrix), len(matrix[0])
        top = zip(repeat(0, w), range(w))
        bottom = zip(repeat(h-1, w), range(w))
        left = zip(range(h), repeat(0, h))
        right = zip(range(h), repeat(w-1, h))
        reach = [[0] * w for _ in range(h)]
        res = []
        visited = set()        
    
        def dfs(i, j):
            if (i,j) in visited:
                return
            
            if reach[i][j] == 3:
                res.append((i,j))
            
            visited.add((i,j))
            for ii, jj in ((i+1, j), (i-1, j), (i, j-1), (i, j+1)):
                if not 0<=ii<h or not 0<=jj<w:
                    continue
                if matrix[ii][jj] >= matrix[i][j]:
                    reach[ii][jj] |= reach[i][j]
                    dfs(ii, jj)
        
        for i, j in chain(top, left):
            reach[i][j] |=1
            dfs(i, j)
        
        visited.clear()
        for i, j in chain(right, bottom):
            reach[i][j] |=2
            dfs(i, j)
        
        return res

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.