# Leetcode Longest Increasing Path in a Matrix problem solution

In this Leetcode Longest Increasing Path in a Matrix problem solution You are given an m x n integers matrix, return the length of the longest increasing path in the 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).

## Problem solution in Python.

```def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
memo={}
def helper(pos):
if pos in memo:
return memo[pos]
i=pos[0]
j=pos[1]
ans=1
for k1,k2 in [[0,1],[0,-1],[1,0],[-1,0]]:
if 0<=i+k1<len(matrix) and 0<=j+k2<len(matrix[0]) and matrix[i][j]>matrix[i+k1][j+k2]:
ans=max(ans,1+helper((i+k1,j+k2)))
memo[pos]=ans
return ans
ans=0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if (i,j) not in memo:
ans=max(ans,helper((i,j)))
return ans
```

## Problem solution in Java.

```class Solution {
public int longestIncreasingPath(int[][] matrix) {
if(matrix.length==0) return 0;
Integer[][] max = new Integer[matrix.length][matrix[0].length];
int maxmax = 0;
for(int i = 0; i<matrix.length; i++){
for(int j = 0; j<matrix[0].length; j++){
dfs(matrix, max, i, j);
maxmax = Math.max(maxmax, max[i][j]);
}
}
return maxmax;
}
public int dfs(int[][] matrix, Integer[][] max, int y, int x){
if(max[y][x]==null){
int max_dist = 0;
int target = matrix[y][x];
if(y-1>=0 && matrix[y-1][x]>target){
dfs(matrix, max, y-1, x);
max_dist = Math.max(max_dist, max[y-1][x]);
}
if(y+1<matrix.length && matrix[y+1][x]>target){
dfs(matrix, max, y+1, x);
max_dist = Math.max(max_dist, max[y+1][x]);
}
if(x-1>=0 && matrix[y][x-1]>target){
dfs(matrix, max, y, x-1);
max_dist = Math.max(max_dist, max[y][x-1]);
}
if(x+1<matrix[0].length && matrix[y][x+1]>target){
dfs(matrix, max, y, x+1);
max_dist = Math.max(max_dist, max[y][x+1]);
}
max[y][x] = max_dist+1;
}
return max[y][x];
}
}
```

## Problem solution in C++.

```class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int m = matrix.size();
if(m==0) return 0;
int n = matrix[0].size();
int max_len = -1;
vector<vector<int>> dp(m,vector<int>(n,-1));
for(int i = 0;i<m;i++)
for(int j = 0;j<n;j++)
max_len = max(max_len,dfs(i,j,matrix,dp));

return max_len;
}
int dfs(int i,int j,vector<vector<int>>& matrix, vector<vector<int>>&dp)
{
if(dp[i][j]!=-1) return dp[i][j];
vector<pair<int,int>> dirs = {{-1,0},{1,0},{0,1},{0,-1}};
int m = matrix.size();
int n = matrix[0].size();
int length = 1;
for(auto dir:dirs)
{
int nextI = i+dir.first;
int nextJ = j+dir.second;
if(nextI<0 || nextI>=m || nextJ<0 || nextJ>=n) continue;
if(matrix[nextI][nextJ] > matrix[i][j])
length = max(length,1+dfs(nextI,nextJ,matrix,dp));
}
dp[i][j] = length;
return dp[i][j];

}
};
```

## Problem solution in C.

```#define MAXN 2048
#define zip(x,y) ((x)*(col)+(y))

int max(int a, int b)
{
return a > b?a:b;
}
int dp[MAXN*MAXN];
int dfs(int x,int y,const int row,const int col,int last,int **mat)
{
if(x >= row || y >= col || x < 0 || y < 0 || mat[x][y] <= last)
return 0;
int t = zip(x,y);
if(dp[t])
return dp[t];
int ret = dfs(x-1,y,row,col,mat[x][y],mat);
ret = max(ret,dfs(x+1,y,row,col,mat[x][y],mat));
ret = max(ret,dfs(x,y-1,row,col,mat[x][y],mat));
ret = max(ret,dfs(x,y+1,row,col,mat[x][y],mat));
return dp[t] = ++ret;
}

int longestIncreasingPath(int** mat, int row, int col) {
int ret = 0;
memset(dp,0,sizeof(int)*zip(row,col));
for(int i = 0; i < row; i++)
for(int j = 0; j < col; j++)
ret = max(ret,dfs(i,j,row,col,mat[i][j] - 1,mat));
return ret;
}
```