Longest Increasing Path — Step-by-Step Visualization

Algorithm Pattern

DFS with Memoization

Key Idea

Since we want to find the longest *increasing* path, there are no cycles (it's a Directed Acyclic Graph). We can use DFS to explore all possible paths from each cell. To avoid redundant computations, we store the result of each cell in a memoization table. The longest path from a cell `(r, c)` is `1 + max(longest paths of neighbors with greater values)`.

Step-by-Step Approach

1. Initialize a `memo` matrix of the same size as the input with 0s.
2. Iterate through every cell `(r, c)` in the matrix.
3. For each cell, perform a DFS to find the longest increasing path starting there.
4. In the DFS:
5. If `memo[r][c] > 0`, return it.
6. Explore all 4 directions. If a neighbor has a value greater than `matrix[r][c]`:
7. `res = max(res, 1 + dfs(neighbor))`.
8. Store the final `res` in `memo[r][c]` and return it.
9. The answer is the maximum value in the `memo` table.

Common Gotchas

• Don't forget the base case: a cell with no strictly greater neighbors has a path length of 1.
• Memoization is mandatory to avoid exponential time complexity.