Longest Increasing Path in a Matrix

hard array dp dfs memoization graph matrix

Problem

Given an m × n integers matrix, return the length of the longest strictly increasing path. From a cell you can move 4-directionally to a strictly greater neighbour.

Inputmatrix = [[9,9,4],[6,6,8],[2,1,1]]

Output4

Path 1 → 2 → 6 → 9.

matrix (rows separated by ';')

def longest_increasing_path(g):
    m, n = len(g), len(g[0])
    memo = [[0]*n for _ in range(m)]
    def dfs(i, j):
        if memo[i][j]: return memo[i][j]
        best = 1
        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < m and 0 <= nj < n and g[ni][nj] > g[i][j]:
                best = max(best, 1 + dfs(ni, nj))
        memo[i][j] = best
        return best
    return max(dfs(i, j) for i in range(m) for j in range(n))

function longestIncreasingPath(g) {
  const m = g.length, n = g[0].length;
  const memo = Array.from({ length: m }, () => new Array(n).fill(0));
  function dfs(i, j) {
    if (memo[i][j]) return memo[i][j];
    let best = 1;
    for (const [di, dj] of [[1,0],[-1,0],[0,1],[0,-1]]) {
      const ni = i + di, nj = j + dj;
      if (ni >= 0 && ni < m && nj >= 0 && nj < n && g[ni][nj] > g[i][j]) {
        best = Math.max(best, 1 + dfs(ni, nj));
      }
    }
    memo[i][j] = best;
    return best;
  }
  let ans = 0;
  for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) ans = Math.max(ans, dfs(i, j));
  return ans;
}

class Solution {
    int[][] g, memo; int m, n;
    int[][] D = {{1,0},{-1,0},{0,1},{0,-1}};
    public int longestIncreasingPath(int[][] g_) {
        g = g_; m = g.length; n = g[0].length;
        memo = new int[m][n];
        int ans = 0;
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) ans = Math.max(ans, dfs(i, j));
        return ans;
    }
    int dfs(int i, int j) {
        if (memo[i][j] != 0) return memo[i][j];
        int best = 1;
        for (int[] d : D) {
            int ni = i + d[0], nj = j + d[1];
            if (ni >= 0 && ni < m && nj >= 0 && nj < n && g[ni][nj] > g[i][j])
                best = Math.max(best, 1 + dfs(ni, nj));
        }
        return memo[i][j] = best;
    }
}

vector<vector<int>> g_, memo_;
int m_, n_;
int D[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int dfs(int i, int j) {
    if (memo_[i][j]) return memo_[i][j];
    int best = 1;
    for (auto& d : D) {
        int ni = i + d[0], nj = j + d[1];
        if (ni >= 0 && ni < m_ && nj >= 0 && nj < n_ && g_[ni][nj] > g_[i][j])
            best = max(best, 1 + dfs(ni, nj));
    }
    return memo_[i][j] = best;
}
int longestIncreasingPath(vector<vector<int>>& g) {
    g_ = g; m_ = g.size(); n_ = g[0].size();
    memo_.assign(m_, vector<int>(n_, 0));
    int ans = 0;
    for (int i = 0; i < m_; i++) for (int j = 0; j < n_; j++) ans = max(ans, dfs(i, j));
    return ans;
}

Explanation

From any cell we can walk to a strictly larger neighbor, and we want the longest such climbing path anywhere in the grid. We solve it with a depth-first search plus memoization, so we never recompute the same cell twice.

The function dfs(i, j) answers one question: "what's the longest increasing path that starts at (i,j)?" Because all moves go to strictly bigger values, the path can never loop back, so the answer is well-defined.

For a cell we look at its four neighbors. For each that is strictly greater, we recurse and take 1 + dfs(neighbor), keeping the best. The result is saved in memo[i][j] so any future visit returns instantly.

We launch dfs from every cell and return the overall maximum. Caching is what makes this fast: each cell's answer is computed only once, giving O(m*n) total.

Example: in [[9,9,4],[6,6,8],[2,1,1]] the path 1 → 2 → 6 → 9 climbs four cells, so the answer is 4.

Time: O(m·n) Space: O(m·n)