Given an m x n</fotn> integers matrix, return *the length of the longest increasing path in* matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

Example 1:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Example 3:

Input: matrix = [[1]]
Output: 1

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 231 - 1

Solution

DFS + memoization

Time complexity : O(mn)
Space complexity : O(mn)

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        rows = matrix.size();
        cols = matrix[0].size();
        memset(dp, 0, sizeof(dp));
        
        int ans = 0;
        for (int r=0; r<rows; ++r) {
            for (int c=0; c<cols; ++c) {
                ans = max(ans, helper(matrix, c, r, -1));
            }
        }
        return ans;
    }
private:
    int dp[200][200], cols, rows;
    int helper(vector<vector<int>> &m, int x, int y, int prev) {
        if (x < 0 || cols <= x || y < 0 || rows <= y || m[y][x] <= prev)
            return 0;
        if (0 != dp[y][x]) return dp[y][x];
        return dp[y][x] = 1 + max({helper(m, x+1, y, m[y][x]),
                                helper(m, x-1, y, m[y][x]),
                                helper(m, x, y+1, m[y][x]),
                                helper(m, x, y-1, m[y][x])});
    }
};