Java simple solution, Memorization, DFS


  • 0
    S
    public class Solution {
        public int longestIncreasingPath(int[][] matrix) {
            if(matrix == null || matrix.length == 0 || matrix[0] == null) {
                return 0;
            }
            int max = -1;
            int n = matrix.length;
            int m = matrix[0].length;
            int[][] memory = new int[n][m];
    
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    max = Math.max(lip(matrix, i, j, n, m, memory), max);
                }
            }
            return max;
        }
    
        //lip is the length of the longest increasing path starting from i, j
        private int lip(int[][] mat, int i, int j, int n, int m, int[][] memory) { 
    	    if(memory[i][j] != 0) {
    	        return memory[i][j];
    	    }
    	    
    	    int max = 1;
    	    if(i+1 < n && mat[i+1][j] > mat[i][j]) {
    	        max = Math.max(max, lip(mat, i+1, j, n, m, memory) + 1);
    	    }
    	    if(i-1 >= 0 && mat[i-1][j] > mat[i][j]) {
    	        max = Math.max(max, lip(mat, i-1, j, n, m, memory) + 1);
    	    }
    	    if(j+1 < m && mat[i][j+1] > mat[i][j]) {
    	        max = Math.max(max, lip(mat, i, j+1, n, m, memory) + 1);
    	    }
    	    if(j-1 >= 0 && mat[i][j-1] > mat[i][j]) {
    	        max = Math.max(max, lip(mat, i, j-1, n, m, memory) + 1);
    	    }
    	    memory[i][j] = max;
    	    return max;
        }
    }

Log in to reply
 

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