# Longest Increasing Path In A Matrix Problem

## Description

LeetCode Problem 329.

Given an m x n 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:

``````1
2
3
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:

``````1
2
3
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:

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

Constraints:

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

## Sample C++ Code

Dynamic programming approach:

• The 2D array dp[i][j] represents the length of longest increasing path starting from (i, j).
• For (i, j) neighbor (i’, j’), if matrix[i’][j’] > matrix[i][j] and dp[i’][j’] has been calculated, then calculate dp[i][j] recursively.
• After all dp[i][j] have been calculated, find the maximum dp[i][j].
``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int rows = matrix.size();
if (!rows) return 0;
int cols = matrix.size();

vector<vector<int>> dp(rows, vector<int>(cols, 0));
std::function<int(int, int)> dfs = [&] (int x, int y) {
if (dp[x][y]) return dp[x][y];
vector<vector<int>> dirs = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
for (auto &dir : dirs) {
int xx = x + dir, yy = y + dir;
if (xx < 0 || xx >= rows || yy < 0 || yy >= cols) continue;
if (matrix[xx][yy] <= matrix[x][y]) continue;
dp[x][y] = std::max(dp[x][y], dfs(xx, yy));
}
return ++dp[x][y];
};

int ret = 0;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
ret = std::max(ret, dfs(i, j));
}
}

return ret;
}
};
``````