Brute force is to do a Depth First Search for every cell to find the longest possible path from it.
It can be optimized by realizing that we only need to visit every cell once, memorizing the length of the longest path starting from it. The longest path from a neighboring cell through this cell will be one more.
class Solution(object): def longestIncreasingPath(self, matrix): """ :type matrix: List[List[int]] :rtype: int """ def DFS_longest_dist(r, c): if longest[r][c]: # already calculated longest distance from this cell return longest[r][c] # init longest distance longest[r][c] = 1 for move in moves: r_next, c_next = r + move, c + move if 0 <= r_next < rows and 0 <= c_next < cols and matrix[r][c] < matrix[r_next][c_next]: # valid move, get longest distance through it, which is # one more than the longest path starting at the next cell dist = DFS_longest_dist(r_next, c_next) + 1 # is it better than what we have? if dist > longest[r][c]: longest[r][c] = dist return longest[r][c] moves = [(0,1),(0,-1),(1,0),(-1,0)] max_dist = 0 rows = len(matrix) cols = 0 if not rows else len(matrix) # will store distance for longest path from given cell # we can use 0 for unvisited because minimum valid dist is 1 longest = [ * cols for _ in range(rows)] # iterate through every cell and calculate longest path through it for r in range(rows): for c in range(cols): if not longest[r][c]: # haven't calculated longest for r,c yet, so do it dist = DFS_longest_dist(r,c) # keep track of max max_dist = max(max_dist, dist) return max_dist