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
1 Answer 1
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.
-
\$\begingroup\$ What do you mean by not passing the initial conditions? Can you rewrite this code after your improvements? \$\endgroup\$noman pouigt– noman pouigt2017年12月11日 03:21:15 +00:00Commented Dec 11, 2017 at 3:21
-
\$\begingroup\$ does this make sense? \$\endgroup\$Oscar Smith– Oscar Smith2017年12月11日 03:32:55 +00:00Commented Dec 11, 2017 at 3:32
-
\$\begingroup\$ It is not compiling. Please check. \$\endgroup\$noman pouigt– noman pouigt2017年12月11日 03:50:29 +00:00Commented Dec 11, 2017 at 3:50
-
\$\begingroup\$ did this fix it? \$\endgroup\$Oscar Smith– Oscar Smith2017年12月11日 03:58:20 +00:00Commented Dec 11, 2017 at 3:58
-
\$\begingroup\$ ideone.com/kGNK2z nope \$\endgroup\$noman pouigt– noman pouigt2017年12月11日 04:03:05 +00:00Commented Dec 11, 2017 at 4:03
Explore related questions
See similar questions with these tags.
def check_boundary(matrix, (row, col)):
is not valid. \$\endgroup\$