# Longest Increasing Path in a Matrix

HARD

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:

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

Constraints:

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

Solution

```class Solution {

private int[][] directions = {{1,0},{0,1},{-1,0},{0,-1}};

public int longestIncreasingPath(int[][] matrix) {

if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return 0;
}
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];
int max_len = 0;
for(int i = 0 ; i < m ; i++){
for(int j = 0 ; j < n ; j++){
max_len = Math.max(max_len, DFS(matrix, dp, m, n, i, j));
}
}
return max_len;
}

private int DFS(int[][] matrix, int[][] dp, int m, int n, int i, int j){
if( i < 0 || i == m || j < 0 || j == n){
return 0;
}
if(dp[i][j] > 0){
return dp[i][j];
}
for(int[] dir : directions){
int ni = i + dir[0];
int nj = j + dir[1];
if(ni >= 0 && ni < m && nj >= 0 && nj < n && matrix[i][j] > matrix[ni][nj]){
dp[i][j] = Math.max(dp[i][j], DFS(matrix, dp, m, n, ni, nj));
}
}
dp[i][j] += 1;
return dp[i][j];
}
}
```

Complexity Analysis

• Time Complexity : `O(mn)`. Each vertex/cell will be calculated once and only once, and each edge will be visited once and only once.
• Space Complexity : `O(mn)`. The cache dominates the space complexity.

Categories: DFS

Tagged as: , ,