Very easy to understand python solution. O(mn)


  • 0
    P

    class Solution(object):

    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        if matrix == None or matrix == []:
            return 0
    
        visited = {} # stores (row,col) as key, L.I.P as value. Kinda like DP
        rowNum = len(matrix)
        colNum = len(matrix[0])
        returnRes = 0
        for row in range(rowNum):
            for col in range(colNum):
                if (row, col) not in visited:
                    res = self.dfsVisit(row, col, matrix, visited, [(row, col)])
                    visited[(row, col)] = res
                    returnRes = max(returnRes, res)
                else:
                    returnRes = max(returnRes, visited[(row, col)])
                    
        return returnRes
    
    def dfsVisit(self, row, col, matrix, visited, ancestors):
        res = 1
        for (row2, col2) in self.findValidCoord(row, col, matrix, ancestors):
            if matrix[row][col] >= matrix[row2][col2]:
                continue
            if (row2, col2) in visited:
                res = max(res, visited[(row2,col2)] + 1)
            else:
                temp = self.dfsVisit(row2, col2, matrix, visited, ancestors + [(row2 , col2)])
                visited[(row2,col2)] = temp
                res = max(res, temp + 1)
        return res
    
    def findValidCoord(self, row, col, matrix, ancestors):
        rowNum = len(matrix)
        colNum = len(matrix[0])
        coords = []
        if (row - 1, col) not in ancestors and row - 1 >= 0:
            coords.append((row - 1, col))
            
        if (row, col-1) not in ancestors and col - 1 >= 0:
            coords.append((row, col - 1))
            
        if (row + 1, col) not in ancestors and row + 1 < rowNum:
            coords.append((row + 1, col))
            
        if (row, col + 1) not in ancestors and col + 1 < colNum:
            coords.append((row, col + 1))
        return coords

Log in to reply
 

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