# Longest Increasing Path in a Matrix from leetcode

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

• your code is broken def check_boundary(matrix, (row, col)): is not valid. Dec 11, 2017 at 4:13

Overall, this is quite clean code. Your use of closures works quite well to hide implementation details. The most obvious thing to change is to remove the class. In python things don't have to be in a class, and nothing is made better here by using one.

Here are some small other improvements This version of check_boundary is smaller, and faster, and arguably cleaner.

def check_boundary(matrix, point):
return 0 < point[0] < len(matrix) and 0 < point[1] < len(matrix[0])


dfs should use keyword arguments so you don't have to pass in initial conditions.

def dfs(current, matrix, visited=set(), memory={}):


This will simplify the end of your main method to

if not matrix:
return 0
maximum = 0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
maximum = max(maximum, dfs((i, j), matrix))
return maximum + 1


This line for direction in [[-1, 0], [1, 0], [0, -1], [0, 1]]: should have Directions factored out, and it should probably be a tuple of tuples instead of a list of lists, for a minor performance boost. Other than that, this looks good.

• What do you mean by not passing the initial conditions? Can you rewrite this code after your improvements? Dec 11, 2017 at 3:21
• does this make sense? Dec 11, 2017 at 3:32
• It is not compiling. Please check. Dec 11, 2017 at 3:50
• did this fix it? Dec 11, 2017 at 3:58
• Dec 11, 2017 at 4:03