find the longest successive path in a matrix

Problem

This is a coding problem which I previously failed in a online test. You are given a matrix filled with positive numbers and the task is build a function that could return the longest successive sequence in this matrix. The sequence must be in ascending order. [
M = left[ begin{array}{rrrrr}
4 & 1 & 3 \
4 & 7 & 6 \
8 & 9 & 10 \
end{array} right]
]

In the example above, the answer should be ([1, 3, 6, 7, 9, 10]).

Approach (DFS)

The most intuitive option must be using deep first search by which we collect all paths start from each value in the matrix and find the one that is longest. Overall, we need two function. The first one is for iteratively test values in matrix and another one is for finding paths recursively.

Code (Python)

• Function 1: all_paths is built for loop
• Function 2: find_path will find the path as larger as possible.

In all_paths, feed every value in the matrix to find_path iteratively. In find_path, recursively test all four cases (up, down, left, right) and return the one that is longest at every step.

class Solution:
    def all_paths(self, matrix):
        if len(matrix) == 0:
            return None
        if len(matrix[0]) == 0:
            return None
        paths = []
        rows, cols = len(matrix), len(matrix[0])
        for i in range(rows):
            for j in range(cols):
                paths.append(self.find_path(matrix, i, j, rows, cols, []))
        return max(paths, key=len)
    
    def find_path(self, matrix, i, j, rows, cols, paths):
        tmp = matrix[i][j]
        matrix[i][j] = 0
        
        # if `all_sets` is empty, there is no next number in this path.
        all_sets = []
        if j + 1 < cols and matrix[i][j + 1] > tmp:
            all_sets.append(self.find_path(matrix, i, j + 1, rows, cols, paths+[tmp]))
        if j - 1 >= 0 and matrix[i][j - 1] > tmp:
            all_sets.append(self.find_path(matrix, i, j - 1, rows, cols, paths+[tmp]))
        if i + 1 < rows and matrix[i + 1][j] > tmp:
            all_sets.append(self.find_path(matrix, i + 1, j, rows, cols, paths+[tmp]))
        if i - 1 >= 0 and matrix[i - 1][j] > tmp:
            all_sets.append(self.find_path(matrix, i - 1, j, rows, cols, paths+[tmp]))
        matrix[i][j] = tmp
        if len(all_sets) == 0:
            return paths + [tmp]
        else:
            return max(all_sets, key=len)
if __name__ == '__main__':
    m = [
        [4, 1, 3],
        [4, 7, 6],
        [8, 9, 10]
    ]
    print(Solution().all_paths(m))

## [1, 3, 6, 7, 9, 10]