Solved this:
Given an integer matrix, find the length of the longest increasing path.
From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).
Solution: do dfs traversal from every greater node to smaller node and store the result. Reuse the result when the same node is traversed again. Take the maximum of all the directions and return the result.
class Solution(object):
def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
def check_boundary(matrix, (row, col)):
if row >= len(matrix) or row < 0:
return False
if col >= len(matrix[0]) or col < 0:
return False
return True
def dfs(current, matrix, visited, memory):
cost = 0
if not check_boundary(matrix, current):
return -1
if current in visited:
return memory[current]
for direction in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
new = current[0] + direction[0], current[1] + direction[1]
visited.add(current)
if check_boundary(matrix, new) and matrix[current[0]][current[1]] > matrix[new[0]][new[1]]:
cost = max(cost, 1 + dfs(new, matrix, visited, memory))
memory[(current)] = cost
return cost
if not matrix:
return 0
maximum = 0
visited, memory = set(), {}
for i in range(len(matrix)):
for j in range(len(matrix[0])):
maximum = max(maximum, dfs((i, j), matrix, visited, memory))
return maximum + 1
def check_boundary(matrix, (row, col)):
is not valid. \$\endgroup\$