# Very easy to understand python solution. O(mn)

• class Solution(object):

``````def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
if matrix == None or matrix == []:
return 0

visited = {} # stores (row,col) as key, L.I.P as value. Kinda like DP
rowNum = len(matrix)
colNum = len(matrix[0])
returnRes = 0
for row in range(rowNum):
for col in range(colNum):
if (row, col) not in visited:
res = self.dfsVisit(row, col, matrix, visited, [(row, col)])
visited[(row, col)] = res
returnRes = max(returnRes, res)
else:
returnRes = max(returnRes, visited[(row, col)])

return returnRes

def dfsVisit(self, row, col, matrix, visited, ancestors):
res = 1
for (row2, col2) in self.findValidCoord(row, col, matrix, ancestors):
if matrix[row][col] >= matrix[row2][col2]:
continue
if (row2, col2) in visited:
res = max(res, visited[(row2,col2)] + 1)
else:
temp = self.dfsVisit(row2, col2, matrix, visited, ancestors + [(row2 , col2)])
visited[(row2,col2)] = temp
res = max(res, temp + 1)
return res

def findValidCoord(self, row, col, matrix, ancestors):
rowNum = len(matrix)
colNum = len(matrix[0])
coords = []
if (row - 1, col) not in ancestors and row - 1 >= 0:
coords.append((row - 1, col))

if (row, col-1) not in ancestors and col - 1 >= 0:
coords.append((row, col - 1))

if (row + 1, col) not in ancestors and row + 1 < rowNum:
coords.append((row + 1, col))

if (row, col + 1) not in ancestors and col + 1 < colNum:
coords.append((row, col + 1))
return coords``````

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