Java recursive with memoization (17ms)


  • 1
    Q
    public class Solution {
        public int longestIncreasingPath(int[][] matrix) {
    		if (matrix.length == 0) return 0;
    		int[][] mem = new int[matrix.length][matrix[0].length];
            int max = 0;
            for (int i=0;i<matrix.length;i++)
            	for (int j=0;j<matrix[0].length;j++)
            		max = Math.max(max, findLongest(i,j,matrix, Integer.MIN_VALUE, 0, mem));
            return max;
        }
    	private int findLongest(int x, int y, int[][] matrix, int val, int count, int[][] mem){
    		if (x<0 || y<0 || x==matrix.length || y==matrix[0].length || matrix[x][y]<=val)
    			return count;
    		
    		if (mem[x][y]>0) return mem[x][y]+count;
    
    		int max = findLongest(x+1, y, matrix, matrix[x][y], count+1, mem);
        	max = Math.max(max,findLongest(x-1, y, matrix, matrix[x][y], count+1, mem));
    		max = Math.max(max, findLongest(x, y+1, matrix, matrix[x][y], count+1, mem));
    		max = Math.max(max, findLongest(x, y-1, matrix, matrix[x][y], count+1, mem));
    		
    		mem[x][y]=max-count;
    		return max;
    	}
    }

  • 0
    Q

    Was able to simplify after getting rid of redudant count variable

    
    public class Solution {
        private static int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        public int longestIncreasingPath(int[][] matrix) {
    		if (matrix.length == 0) return 0;
    		int[][] mem = new int[matrix.length][matrix[0].length];
            int max = 0;
            for (int i=0;i<matrix.length;i++)
            	for (int j=0;j<matrix[0].length;j++)
            		max = Math.max(max, helper(i,j,matrix, -1, mem));
            return max;
        }
    	private int helper(int x, int y, int[][] mat, int oldVal, int[][] mem){
    		if (x<0||y<0||x==mat.length||y==mat[0].length||mat[x][y]<=oldVal) return 0;
    		if (mem[x][y]>0) return mem[x][y];
            for (int[] dir : dirs)
    		    mem[x][y]=Math.max(mem[x][y],helper(x+dir[0],y+dir[1],mat,mat[x][y],mem)+1);
    		return mem[x][y]; 
    	}
    }
    
    

Log in to reply
 

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