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: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s