4
\$\begingroup\$

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
asked Dec 11, 2017 at 2:50
\$\endgroup\$
1
  • \$\begingroup\$ your code is broken def check_boundary(matrix, (row, col)): is not valid. \$\endgroup\$ Commented Dec 11, 2017 at 4:13

1 Answer 1

1
\$\begingroup\$

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.

answered Dec 11, 2017 at 3:05
\$\endgroup\$
8
  • \$\begingroup\$ What do you mean by not passing the initial conditions? Can you rewrite this code after your improvements? \$\endgroup\$ Commented Dec 11, 2017 at 3:21
  • \$\begingroup\$ does this make sense? \$\endgroup\$ Commented Dec 11, 2017 at 3:32
  • \$\begingroup\$ It is not compiling. Please check. \$\endgroup\$ Commented Dec 11, 2017 at 3:50
  • \$\begingroup\$ did this fix it? \$\endgroup\$ Commented Dec 11, 2017 at 3:58
  • \$\begingroup\$ ideone.com/kGNK2z nope \$\endgroup\$ Commented Dec 11, 2017 at 4:03

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.