Longest Increasing Path in a Matrix

HardDynamic Programming

Find the length of the longest strictly increasing path in a matrix, moving only up, down, left, or right.

Constraints

1 <= m, n <= 200
0 <= matrix[i][j] <= 2^31 - 1

DFS with memoization

Time O(m * n)Space O(m * n)

The longest increasing path starting at a cell depends only on its larger neighbors, so it can be memoized. DFS each cell once, caching results, and take the global maximum.

#include <bits/stdc++.h>
using namespace std;

int longestIncreasingPath(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size(), best = 0;
    vector<vector<int>> memo(m, vector<int>(n, 0));
    int dirs[5] = {0, 1, 0, -1, 0};
    function<int(int,int)> dfs = [&](int r, int c) -> int {
        if (memo[r][c]) return memo[r][c];
        int best1 = 1;
        for (int d = 0; d < 4; d++) {
            int nr = r + dirs[d], nc = c + dirs[d + 1];
            if (nr >= 0 && nc >= 0 && nr < m && nc < n && matrix[nr][nc] > matrix[r][c])
                best1 = max(best1, 1 + dfs(nr, nc));
        }
        return memo[r][c] = best1;
    };
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            best = max(best, dfs(i, j));
    return best;
}