Python solution, memoization dp, 288ms


  • 31
    K

    We can find longest decreasing path instead, the result will be the same. Use dp to record previous results and choose the max dp value of smaller neighbors.

    def longestIncreasingPath(self, matrix):
        def dfs(i, j):
            if not dp[i][j]:
                val = matrix[i][j]
                dp[i][j] = 1 + max(
                    dfs(i - 1, j) if i and val > matrix[i - 1][j] else 0,
                    dfs(i + 1, j) if i < M - 1 and val > matrix[i + 1][j] else 0,
                    dfs(i, j - 1) if j and val > matrix[i][j - 1] else 0,
                    dfs(i, j + 1) if j < N - 1 and val > matrix[i][j + 1] else 0)
            return dp[i][j]
    
        if not matrix or not matrix[0]: return 0
        M, N = len(matrix), len(matrix[0])
        dp = [[0] * N for i in range(M)]
        return max(dfs(x, y) for x in range(M) for y in range(N))

  • 0
    Z

    Beautiful. Thank you.


  • 0
    R

    As clear as pseudo code! Thanks.


  • -1
     definning dfs(i,j) method inside the function longestIncreasingPath(self, matrix), it may cuase some problems!
        And maybe you think your code is elegant ,but In fact this code style slows down the speed of
        function longestIncreasingpath!

  • 0
    K

    very clear and elegant code! Thanks for sharing~


  • 1

    Why do you search for longest decreasing instead of longest increasing? What is the difference?


  • 1
    P

    If I find the longest increasing path without memoization, it works but with this implementation of memoization, only the longest decreasing path works. Some explanation from the OP would be helpful.

    EDIT: I just made my code work (it was simply buggy). The logic is that the largest increasing path is also the largest decreasing. He just happened to search for the largest decreasing one.

    Here's my code:

    class Solution(object):
        def longestIncreasingPath(self, matrix):
            def helper(i, j, matrix):
                if not self.memo[i][j]:
                    val = matrix[i][j]
                    self.memo[i][j] = 1 + max(
                        helper(i+1, j, matrix) if i < self.m - 1 and val < matrix[i+1][j] else 0,
                        helper(i-1, j, matrix) if i and val < matrix[i-1][j] else 0,
                        helper(i, j+1, matrix) if j < self.n - 1 and val < matrix[i][j+1] else 0,
                        helper(i, j-1, matrix) if j and val < matrix[i][j-1] else 0)
                return self.memo[i][j]
            if not matrix or not matrix[0]: return 0
            self.m, self.n = len(matrix), len(matrix[0])
            self.memo = [[0]*self.n for _ in range(self.m)]
            return max(helper(i, j, matrix) for i in range(self.m) for j in range(self.n))

  • 0
    P
    This post is deleted!

  • 1
    W

    my code ,same recursive way, but time exceed :-( though I can't feel much difference

    class Solution(object):
        def longestIncreasingPath(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: int
            """
            if not matrix:
                return 0
            w=len(matrix[0])
            h=len(matrix)
            bank=[[0]*w for i in range(h)]
            for i in range(h):
                for j in range(w):
                    stack=[(i,j,0)]
                    while stack:
                        iin,jin,k=stack.pop(0)
                        for x,y in (iin+1,jin),(iin-1,jin),(iin,jin+1),(iin,jin-1):
                            if -1<x<h and -1<y<w and matrix[x][y]>matrix[iin][jin]:
                                stack.append((x,y,k+1))
                                bank[x][y]=max(bank[x][y],k+1)
            return max(max(a)for a in bank)+1
    

  • 0

    @weiheng4
    Almost the same.

    def longestIncreasingPath(self, M):
            if not any(M): return 0
            d = {}
            def check(i, j):
                if not (i, j) in d:
                    d[(i, j)] = max(check(x, y) 
                        if 0 <= x < len(M) and 0 <= y < len(M[0]) and M[x][y] > M[i][j] else 0
                        for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]) + 1
                return d[(i, j)]
            return max(check(i, j) for i in range(len(M)) for j in range(len(M[0])))

Log in to reply
 

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