Longest Increasing Path in a Matrix

1class Solution:
2    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
3
4        longest_paths = [[None for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
5
6        def dfs(x, y):
7            if longest_paths[y][x]:
8                return longest_paths[y][x]
9            
10            path_length = 1
11            last_node_val = matrix[y][x]
12            # Left
13            if x - 1 >= 0:
14                if matrix[y][x-1] > last_node_val:
15                    path_length = max(path_length, 1 + dfs(x-1, y))
16            
17            # Right
18            if x + 1 < len(matrix[0]):
19                if matrix[y][x+1] > last_node_val:
20                    path_length = max(path_length, 1 + dfs(x+1, y))
21            
22            # Up
23            if y - 1 >= 0:
24                if matrix[y-1][x] > last_node_val:
25                    path_length = max(path_length, 1 + dfs(x, y-1))
26            
27            # Bottom
28            if y + 1 < len(matrix):
29                if matrix[y+1][x] > last_node_val:
30                    path_length = max(path_length, 1 + dfs(x, y+1))
31            
32            longest_paths[y][x] = path_length
33            return path_length
34        
35        res = 0
36        # Add all nodes as starting points
37        for y in range(0, len(matrix)):
38            for x in range(0, len(matrix[y])):
39                res = max(res, dfs(x, y))
40
41        return res
42            
43