Longest Increasing Path in a Matrix

hardTests passed 2026-11-11v1.0.0
TC: O(M * N)|SC: O(M * N)
2D DPGraphsOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Strictly increasing edges `matrix[nr][nc] > matrix[r][c]` guarantee the implicit graph is a **DAG** (no cycles are possible!). Therefore no `visited` set is needed — plain memoized DFS (`cache[r][c]`) computes every cell’s longest path once.

2. Complexity Bounds & Proof

Because strictly increasing paths cannot revisit a cell, every vertex out-edge is evaluated once and memoized in O(MN).

3. Minimal Idiomatic Code

def longestIncreasingPath(matrix: list[list[int]]) -> int:
    R, C = len(matrix), len(matrix[0])
    memo = [[0] * C for _ in range(R)]
    def dfs(r: int, c: int) -> int:
        if memo[r][c]:
            return memo[r][c]
        best = 1
        cur = matrix[r][c]
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and matrix[nr][nc] > cur:
                best = max(best, 1 + dfs(nr, nc))
        memo[r][c] = best
        return best
    return max(dfs(r, c) for r in range(R) for c in range(C))

4. Failure Modes & Interview Follow-ups

Pitfalls:- Adding a mutable `visited` bitmask breaks memoization correctness because different entry paths wouldn’t share cached results. - Using `>=` instead of `>` creates cycles on equal-value adjacent cells.
Follow-ups:- Iterative topological peel (Kahn’s algorithm on grid cells ordered by uphill indegree) runs layer-by-layer without recursion stack overflow.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Pacific Atlantic Water Flow (O(M * N))Longest Increasing Subsequence (O(N log N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.