Python solution with detailed explanation


  • 0
    G

    Solution

    Longest Increasing Path in a Matrix https://leetcode.com/problems/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.

    Memoization

    • 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
    L

    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.