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 = [[1]]
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[0].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)

Leave a Comment

Your email address will not be published. Required fields are marked *