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\$
  • \$\begingroup\$ your code is broken def check_boundary(matrix, (row, col)): is not valid. \$\endgroup\$ – Oscar Smith Dec 11 '17 at 4:13
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\$
  • \$\begingroup\$ What do you mean by not passing the initial conditions? Can you rewrite this code after your improvements? \$\endgroup\$ – noman pouigt Dec 11 '17 at 3:21
  • \$\begingroup\$ does this make sense? \$\endgroup\$ – Oscar Smith Dec 11 '17 at 3:32
  • \$\begingroup\$ It is not compiling. Please check. \$\endgroup\$ – noman pouigt Dec 11 '17 at 3:50
  • \$\begingroup\$ did this fix it? \$\endgroup\$ – Oscar Smith Dec 11 '17 at 3:58
  • \$\begingroup\$ ideone.com/kGNK2z nope \$\endgroup\$ – noman pouigt Dec 11 '17 at 4:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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