Longest Increasing Path in a Matrix

Problem: Longest Increasing Path in a Matrix

We can do depth-first search at each position in the matrix. At each position, we check whether there are bigger neighbors. If so, we can get length of longest increasing path starting at that neighbor and get length of LCP starting at current position by increment 1. We take longest path from LCPs starting from bigger neighbors. After we deal with all positions, we can get length of LCPs starting from each position, thus we can get our answer. To avoid repeating calculation at same position, we can use memoization.

Code in Python:

class Solution(object):
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        if not matrix: return 0

        m, n = len(matrix), len(matrix[0])

        inc = [[None] * n for i in xrange(m)]

        def getInc(x, y):
            if inc[x][y] != None: return inc[x][y]
            inc[x][y] = 0
            if x > 0 and matrix[x][y] < matrix[x-1][y]: inc[x][y] = max(inc[x][y], getInc(x-1, y)+1)
            if y > 0 and matrix[x][y] < matrix[x][y-1]: inc[x][y] = max(inc[x][y], getInc(x, y-1)+1)
            if x < m-1 and matrix[x][y] < matrix[x+1][y]: inc[x][y] = max(inc[x][y], getInc(x+1, y)+1)
            if y < n-1 and matrix[x][y] < matrix[x][y+1]: inc[x][y] = max(inc[x][y], getInc(x, y+1)+1)
            return inc[x][y]

        for i in xrange(m):
            for j in xrange(n):
                getInc(i, j)

        ans = 0
        for i in xrange(m):
            ans = max(ans, max(inc[i]))
        return ans+1