Problem statement

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

Solution

This problem is dynamic programming problem, the problem is to understand how to traverse our matrix. Actually we can look at this problem as directed graph, and the goal is to find the longest path. One way to do it is to use bfs, where we start from all nodes with outgoing degree equel to 0 and then traverse all nodes from which we can reach these nodes and so on. Another way is to use dynamic programming (sometimes it is called memoisation here, because it is not the usual way to traverse elements), but in fact it is just usual dynamic programming.

  1. Let dfs(x, y) be an answer for cell with coordinates (x, y). In the beginning we define it as 1: there is a path of length 1 for sure.
  2. Then we check all neighbours and check answers for them and if we can continue path, we update ans.
  3. In the end we check values for all cells and return the maximum one.

Notice, how short and clean you code will be when we use memoisation here, we do not need to bother where to start our traversal, in the end we always reach bottom nodes and they will be traversed first.

Complexity

Time complexity is just O(mn), because we have this number of states and for each state we have at most 4 transitions. Space complexity is the same.

Code

class Solution:
    def longestIncreasingPath(self, matrix):
        m, n = len(matrix), len(matrix[0])
        neibs = [(0, -1), (0, 1), (1, 0), (-1, 0)]
        
        @lru_cache(None)
        def dfs(x, y):
            ans = 1
            for dx, dy in neibs:
                if 0 <= x+dx < m and 0 <= y+dy <n and matrix[x+dx][y+dy] < matrix[x][y]:
                    ans = max(ans, dfs(x+dx, y+dy) + 1) 
            return ans
        
        return max(dfs(i, j) for i, j in product(range(m), range(n)))