Python solution with detailed explanation

  • 0


    Longest Increasing Path in a Matrix

    Brute Force

    • Brute force will be to run DFS at each node and choose the next neighbor based on the condition that its value is more than the current one. You will need a visited matrix here to prevent recomputation.


    • You can use a memoization cache. The beauty is that once you do that, you no longer even need a visited matrix.
    from collections import defaultdict
    class Solution(object):
        def longestIncreasingPath(self, matrix):
            :type matrix: List[List[int]]
            :rtype: int
            if matrix == []:
                return 0
            M, N, result = len(matrix), len(matrix[0]), 0
            cache = defaultdict(lambda: defaultdict(int))
            for i in range(M):
                for j in range(N):
                    result = max(result, self.dfs(i,j, matrix, cache))
            return result
        def dfs(self, i, j, matrix, cache):
            if i in cache and j in cache[i]:
                return cache[i][j]
            candidates, cache[i][j] = ((i+1, j), (i-1, j), (i, j+1), (i, j-1)), 1
            for a,b in candidates:
                if 0 <= a < len(matrix) and 0 <= b < len(matrix[0]) and matrix[i][j] < matrix[a][b]:
                    cache[i][j] = max(cache[i][j], 1+self.dfs(a,b,matrix,cache))
            return cache[i][j]

  • 0

    Faster to use a 2d matrix for storage rather than a dictionary

Log in to reply

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