Python DFS with memorization, with explanation


  • 0
    R

    Brute force is to do a Depth First Search for every cell to find the longest possible path from it.

    It can be optimized by realizing that we only need to visit every cell once, memorizing the length of the longest path starting from it. The longest path from a neighboring cell through this cell will be one more.

    class Solution(object):
        def longestIncreasingPath(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: int
            """
            
            def DFS_longest_dist(r, c):
                if longest[r][c]:
                    # already calculated longest distance from this cell
                    return longest[r][c]
                
                # init longest distance
                longest[r][c] = 1
                
                for move in moves:
                    r_next, c_next = r + move[0], c + move[1]
                    if 0 <= r_next < rows and 0 <= c_next < cols and matrix[r][c] < matrix[r_next][c_next]:
                        # valid move, get longest distance through it, which is
                        # one more than the longest path starting at the next cell
                        dist = DFS_longest_dist(r_next, c_next) + 1
                        
                        # is it better than what we have?
                        if dist > longest[r][c]:
                            longest[r][c] = dist
                        
                return longest[r][c]
            
            moves = [(0,1),(0,-1),(1,0),(-1,0)]
            max_dist = 0
            
            rows = len(matrix)
            cols = 0 if not rows else len(matrix[0])
            
            # will store distance for longest path from given cell
            # we can use 0 for unvisited because minimum valid dist is 1
            longest = [[0] * cols for _ in range(rows)]
            
            # iterate through every cell and calculate longest path through it
            for r in range(rows):
                for c in range(cols):
                    if not longest[r][c]:
                        # haven't calculated longest for r,c yet, so do it
                        dist = DFS_longest_dist(r,c)
                        # keep track of max
                        max_dist = max(max_dist, dist)
    
            return max_dist
    

Log in to reply
 

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