# Longest Increasing Path in a Matrix

Hi Geeks, in this article, we going to solve Longest Increasing Path in a Matrix problem by using DFS(Depth First Search) Approach. Lets jump into given problem.

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 = []
Output: 1

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

## Solution

### Java Program

``````class Solution {

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

int[][] cache;

public int longestIncreasingPath(int[][] matrix) {
if(matrix == null || matrix.length == 0) return 0;

int row = matrix.length;
int col = matrix.length;

cache = new int[row][col];

int longestPath = 0;

for(int i=0;i= 0 && newIndex_j >= 0 && newIndex_i < row && newIndex_j < col &&
matrix[newIndex_i][newIndex_j] > matrix[currentIndex_i][currentIndex_j])
{
int currentMax = dfs(matrix,row,col,newIndex_i,newIndex_j);
max = Math.max(max,currentMax);
}
}

cache[currentIndex_i][currentIndex_j] = max+1;
return max+1;
}
}``````

Time Complexity: O(m x n)

Space Complexity: O(m x n)