Longest Increasing Path in a Matrix

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> memo(m, vector<int>(n, 0));
        function<int(int,int)> dfs = [&](int r, int c) {
            if (memo[r][c]) return memo[r][c];
            int best = 1;
            int dr[4] = {1,-1,0,0}, dc[4] = {0,0,1,-1};
            for (int k = 0; k < 4; ++k) {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n || mat[nr][nc] <= mat[r][c]) continue;
                best = max(best, 1 + dfs(nr, nc));
            }
            return memo[r][c] = best;
        };
        int ans = 0;
        for (int r = 0; r < m; ++r) for (int c = 0; c < n; ++c) ans = max(ans, dfs(r, c));
        return ans;
    }
};

func longestIncreasingPath(mat [][]int) int {
    m, n := len(mat), len(mat[0])
    memo := make([][]int, m)
    for i := range memo {
        memo[i] = make([]int, n)
    }
    dr := [4]int{1, -1, 0, 0}
    dc := [4]int{0, 0, 1, -1}
    var dfs func(r, c int) int
    dfs = func(r, c int) int {
        if memo[r][c] != 0 {
            return memo[r][c]
        }
        best := 1
        for k := 0; k < 4; k++ {
            nr, nc := r+dr[k], c+dc[k]
            if nr < 0 || nr >= m || nc < 0 || nc >= n || mat[nr][nc] <= mat[r][c] {
                continue
            }
            if v := 1 + dfs(nr, nc); v > best {
                best = v
            }
        }
        memo[r][c] = best
        return best
    }
    ans := 0
    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            if v := dfs(r, c); v > ans {
                ans = v
            }
        }
    }
    return ans
}

from typing import List

class Solution:
    def longestIncreasingPath(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        memo = [[0] * n for _ in range(m)]
        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))

        def dfs(r: int, c: int) -> int:
            if memo[r][c]:
                return memo[r][c]
            best = 1
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and mat[nr][nc] > mat[r][c]:
                    best = max(best, 1 + dfs(nr, nc))
            memo[r][c] = best
            return best

        ans = 0
        for r in range(m):
            for c in range(n):
                ans = max(ans, dfs(r, c))
        return ans

function longestIncreasingPath(mat) {
    const m = mat.length, n = mat[0].length;
    const memo = Array.from({ length: m }, () => new Array(n).fill(0));
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    const dfs = (r, c) => {
        if (memo[r][c]) return memo[r][c];
        let best = 1;
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && mat[nr][nc] > mat[r][c]) {
                best = Math.max(best, 1 + dfs(nr, nc));
            }
        }
        memo[r][c] = best;
        return best;
    };
    let ans = 0;
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            ans = Math.max(ans, dfs(r, c));
        }
    }
    return ans;
}

class Solution {
    private int[][] mat;
    private int[][] memo;
    private int m, n;
    private static final int[] DR = {1, -1, 0, 0};
    private static final int[] DC = {0, 0, 1, -1};

    public int longestIncreasingPath(int[][] mat) {
        this.mat = mat;
        m = mat.length;
        n = mat[0].length;
        memo = new int[m][n];
        int ans = 0;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                ans = Math.max(ans, dfs(r, c));
            }
        }
        return ans;
    }

    private int dfs(int r, int c) {
        if (memo[r][c] != 0) return memo[r][c];
        int best = 1;
        for (int k = 0; k < 4; k++) {
            int nr = r + DR[k], nc = c + DC[k];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || mat[nr][nc] <= mat[r][c]) continue;
            best = Math.max(best, 1 + dfs(nr, nc));
        }
        memo[r][c] = best;
        return best;
    }
}

function longestIncreasingPath(mat: number[][]): number {
    const m = mat.length, n = mat[0].length;
    const memo: number[][] = Array.from({ length: m }, () => new Array(n).fill(0));
    const dirs: [number, number][] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    const dfs = (r: number, c: number): number => {
        if (memo[r][c]) return memo[r][c];
        let best = 1;
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && mat[nr][nc] > mat[r][c]) {
                best = Math.max(best, 1 + dfs(nr, nc));
            }
        }
        memo[r][c] = best;
        return best;
    };
    let ans = 0;
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            ans = Math.max(ans, dfs(r, c));
        }
    }
    return ans;
}