Longest Increasing Path In a Matrix: the idea to remember.

The core insight

Cache the longest path starting at each cell and recurse only to strictly larger neighbors.

Why it works

Strict increase forbids cycles, so each cell's answer depends on a directed acyclic set of larger neighbors.

The mistake to avoid

Equal values cannot extend the path. Memoization must be shared across searches from all starting cells.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Cache the longest path starting at each cell and recurse only to strictly larger neighbors.
public int longestIncreasingPath(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    int[][] dp = new int[m][n];
    for (int d[] : dp) Arrays.fill(d, -1);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (dp[i][j] == -1) dfs(matrix, dp, m, n, i, j, -1);
        }
    }
    int max = Integer.MIN_VALUE;
    for (int[] d : dp) {
        for (int i : d) max = Math.max(i, max);
    }
    return max;
}

public int dfs(
    int[][] matrix,
    int[][] dp,
    int m,
    int n,
    int i,
    int j,
    int parent
) {
    if (
        i >= m || j >= n || i < 0 || j < 0 || matrix[i][j] <= parent
    ) return 0;
    parent = matrix[i][j];
    if (dp[i][j] != -1) return dp[i][j];
    int left = dfs(matrix, dp, m, n, i, j - 1, parent);
    int right = dfs(matrix, dp, m, n, i, j + 1, parent);
    int bottom = dfs(matrix, dp, m, n, i + 1, j, parent);
    int top = dfs(matrix, dp, m, n, i - 1, j, parent);
    dp[i][j] = 1 + Math.max(Math.max(left, right), Math.max(top, bottom));
    return dp[i][j];
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection