Longest Increasing Path in a Matrix

def longest_increasing_path(matrix):
    m, n = len(matrix), len(matrix[0])
    memo = {}
    def best(r, c):
        if (r, c) not in memo:
            top = 1
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:
                    top = max(top, 1 + best(nr, nc))
            memo[(r, c)] = top
        return memo[(r, c)]
    return max(best(r, c) for r in range(m) for c in range(n))

Longest Increasing Path in a Matrix. Find the longest path in a grid where each step goes up, down, left or right to a strictly bigger number. No diagonals, no wrapping around.

Here, the longest climb is one, two, six, nine: length four. In this grid, three, four, five, six: also four. A single cell is a path of one.

The naive way searches from every cell and remembers nothing, walking the same uphill paths again and again. A ten by ten grid takes over seven hundred thousand calls: exponential.

The key idea: remember each cell's answer. Its best path is one, plus the best of its bigger neighbours. No visited set is needed: a path that only climbs can never loop, so the grid is a directed acyclic graph.

In code, a cached search tries four directions, keeps bigger neighbours, and stores one plus the best. The answer is the max over every cell.

Now the first grid, row by row. Both nines have nothing bigger: one each. Four climbs to eight, worth one, or to nine: two. Each six climbs to a nine: two. Two climbs to six: three. The middle one can reach six or two, both already remembered: no new search, just one plus three, four. The last one climbs to eight: two. The best is four.

Each cell is solved once, checking four neighbours: order M N time and space. A topological sort, peeling layers, gives the same answer.

Only climb up, remember every cell, take the best. That's Longest Increasing Path in a Matrix.