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
\$\endgroup\$
1
  • \$\begingroup\$ your code is broken def check_boundary(matrix, (row, col)): is not valid. \$\endgroup\$ 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.