Neat Java DFS solution with Memoization


  • 4

    Starting with each element of matrix and also remember the longest length starting from each element to remove duplicate computations.

    The tricky part is a visited map is not required (cause visited value is always smaller). And this also guarantees that the cache will work, once a longest length is computed for an element, the value preserves no matter how previous sequence lands here (as it always follow the increasing order).

    public class Solution {
        
        private int dfs(int[][] matrix, int i, int j, int[][] cache) {
            if(cache[i][j] > 0)
                return cache[i][j];
            int longest = 0;
            if(i>0 && matrix[i][j]<matrix[i-1][j]) 
                longest = Math.max(longest, dfs(matrix, i-1, j, cache));
            if(j>0 && matrix[i][j]<matrix[i][j-1])
                longest = Math.max(longest, dfs(matrix, i, j-1, cache));
            if(i<matrix.length-1 && matrix[i][j]<matrix[i+1][j])
                longest = Math.max(longest, dfs(matrix, i+1, j, cache));
            if(j<matrix[0].length-1 && matrix[i][j]<matrix[i][j+1])
                longest = Math.max(longest, dfs(matrix, i, j+1, cache));
            cache[i][j] = longest+1;
            return longest+1;
        }
        
        public int longestIncreasingPath(int[][] matrix) {
            if(matrix.length==0)
                return 0;
            int[][] cache = new int[matrix.length][matrix[0].length];
            int longest = 0;
            for(int i=0; i<matrix.length; i++)
                for(int j=0; j<matrix[0].length; j++)
                    longest = Math.max(longest, dfs(matrix, i, j, cache));
            return longest;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.