## Algorithm

Problem Name: 329. Longest Increasing Path in a Matrix

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:

```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`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#define IDX(I, J, L) ((I) * (L) + (J))
int depth(int **matrix, int rowsz, int colsz, int *dep, int row, int col) {
int s, x, z, y;
int d = 0;

d = dep[IDX(row, col, colsz)];
if (d) {
return d;
}

if (row == 0 || matrix[row][col]  < = matrix[row - 1][col]) {
s = 1;
} else {
s = depth(matrix, rowsz, colsz, dep, row - 1, col) + 1;
}

if (row == rowsz - 1 || matrix[row][col]  < = matrix[row + 1][col]) {
x = 1;
} else {
x = depth(matrix, rowsz, colsz, dep, row + 1, col) + 1;
}

if (col == 0 || matrix[row][col]  < = matrix[row][col - 1]) {
z = 1;
} else {
z = depth(matrix, rowsz, colsz, dep, row, col - 1) + 1;
}

if (col == colsz - 1 || matrix[row][col]  < = matrix[row][col + 1]) {
y = 1;
} else {
y = depth(matrix, rowsz, colsz, dep, row, col + 1) + 1;
}

d = s;
d = d > x ? d : x;
d = d > z ? d : z;
d = d > y ? d : y;
dep[IDX(row, col, colsz)] = d;

return d;
}

int longestIncreasingPath(int** matrix, int matrixRowSize, int matrixColSize) {
int i, j;
int *dep;
int d, max = 0;

if (matrixRowSize  < = 0 || matrixColSize <= 0) return 0;

dep = calloc(matrixRowSize * matrixColSize, sizeof(int));
//assert(dep);

for (i = 0; i  <  matrixRowSize; i ++) {
for (j = 0; j  <  matrixColSize; j ++) {
d = depth(matrix, matrixRowSize, matrixColSize, dep, i, j);
max = max  <  d ? d : max;
}
}

free(dep);

return max;
}
``````
Copy The Code &

Input

cmd
matrix = [[9,9,4],[6,6,8],[2,1,1]]

Output

cmd
4

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
int m = matrix.size() , n = matrix[0].size();
vector<vector < int>>dp(m, vector<int>(n));
vector < vector<int>>visited(m, vector<int>(n));
int maxlen = 0;
for(int i = 0; i  <  m; i++)
for(int j = 0; j  <  n; j++)
maxlen = max(maxlen, DFS(matrix, visited, dp, i, j, m, n));
return maxlen;
}

int DFS(vector < vector<int>>& matrix, vector < vector<int>>& visited, vector < vector<int>>& dp, int r, int c, int m, int n){
if(visited[r][c]) return 0;
if(dp[r][c]) return dp[r][c];
visited[r][c] = 1;
int up(1), down(1), left(1), right(1>;
if(r - 1 >= 0 && matrix[r - 1][c] > matrix[r][c])     up = DFS(matrix, visited, dp, r - 1, c, m, n) + 1;
if(r + 1  <  m  && matrix[r + 1][c] > matrix[r][c])   down = DFS(matrix, visited, dp, r + 1, c, m, n) + 1;
if(c - 1 >= 0 && matrix[r][c - 1] > matrix[r][c])   left = DFS(matrix, visited, dp, r, c - 1, m, n) + 1;
if(c + 1  <  n  && matrix[r][c + 1] > matrix[r][c])  right = DFS(matrix, visited, dp, r, c + 1, m, n) + 1;
visited[r][c] = 0;
dp[r][c] = max(up, max(down, max(left, right)));
return dp[r][c];
}
};
``````
Copy The Code &

Input

cmd
matrix = [[9,9,4],[6,6,8],[2,1,1]]

Output

cmd
4

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
private final int[][] DIRS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

public int longestIncreasingPath(int[][] matrix) {
int numRows = matrix.length;
int numCols = matrix[0].length;
int maxPathLength = 0;
int[][] cache = new int[numRows][numCols];
for (int i = 0; i  <  numRows; i++) {
for (int j = 0; j  <  numCols; j++) {
maxPathLength = Math.max(maxPathLength, helper(matrix, numRows, numCols, i, j, cache));
}
}
return maxPathLength;
}

private int helper(int[][] matrix, int numRows, int numCols, int i, int j, int[][] cache) {
if (cache[i][j] != 0) {
return cache[i][j];
}
for (int[] dir : DIRS) {
int x = i + dir[0];
int y = j + dir[1];
if (x >= 0 && y >= 0 && x  <  numRows && y < numCols && matrix[x][y] > matrix[i][j]) {
cache[i][j] = Math.max(cache[i][j], helper(matrix, numRows, numCols, x, y, cache));
}
}
return ++cache[i][j];
}
}
``````
Copy The Code &

Input

cmd
matrix = [[3,4,5],[3,2,6],[2,2,1]]

Output

cmd
4

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const longestIncreasingPath = function(matrix) {
const m = matrix.length, n = matrix[0].length
let res = 1

const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
const memo = Array.from({ length: m }, () => Array(n).fill(0))
for(let i = 0; i  <  m; i++) {
for(let j = 0; j  <  n; j++) {
const len = dfs(i, j)
res = Math.max(res, len)
}
}

return res

function dfs(i, j) {
const v = matrix[i][j]
if(memo[i][j] !== 0) return memo[i][j]
let len = 1
for(const [dx, dy] of dirs) {
const nx = i + dx, ny = j + dy
if(nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] > v) {
const tmp = 1 + dfs(nx, ny)
len = Math.max(len, tmp)
}
}

memo[i][j] = len
return len
}
};
``````
Copy The Code &

Input

cmd
matrix = [[3,4,5],[3,2,6],[2,2,1]]

Output

cmd
4

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def longestIncreasingPath(self, matrix):
def dfs(i, j):
if not dp[i][j]:
dp[i][j] = 1+max((dfs(x,y) for x,y in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)) if 0 <=x matrix[i][j]),default=0)
return dp[i][j]
m, n, = len(matrix), len(matrix and matrix[0])
dp = [[0] * n for _ in range(m)]
return max((dfs(i,j) for i in range(m) for j in range(n)),default=0)
``````
Copy The Code &

Input

cmd
matrix = [[1]]

Output

cmd
1

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0329_LongestIncreasingPathInAMatrix
{
private readonly static int[][] dirs = new int[][] { new int[] { 0, 1 }, new int[] { 1, 0 }, new int[] { 0, -1 }, new int[] { -1, 0 } };

public int LongestIncreasingPath(int[][] matrix)
{
if (matrix.Length == 0) return 0;
int M = matrix.Length, N = matrix[0].Length;
var cache = new int[M, N];

var maxValue = 0;
for (int i = 0; i  <  M; i++)
for (int j = 0; j  <  N; j++)
maxValue = Math.Max(maxValue, DFS(cache, matrix, M, N, i, j));
return maxValue + 1;
}

private int DFS(int[,] cache, int[][] matrix, int M, int N, int i, int j)
{
if (cache[i, j] != 0) return cache[i, j];
foreach (var dir in dirs)
{
int x = i + dir[0], y = j + dir[1];
if (0  < = x && x < M && 0 <= y && y < N)
if (matrix[x][y] > matrix[i][j])
cache[i, j] = Math.Max(cache[i, j], DFS(cache, matrix, M, N, x, y) + 1);
}
return cache[i, j];
}
}
}
``````
Copy The Code &

Input

cmd
matrix = [[1]]

Output

cmd
1