# Python solution with detailed explanation

• 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]
``````

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

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