Concise DFS solution


  • 0
    S
    public int longestIncreasingPath(int[][] matrix) {
    	int h = matrix.length;
    	if (h < 1) return 0;
    	int w = matrix[0].length;
    		
    	int[][] mem = new int[h][w];
    	int max = 0;
    	for (int i = 0; i < h; i++) {
    		for (int j = 0; j < w; j++) {
    			max = Math.max(max, mem[i][j]!=0 ? mem[i][j] : dfs(matrix, mem, i, j, h, w));
    		}
    	}
    	return max;
    }
    	
    private int dfs(int[][] matrix, int[][] mem, int i, int j, int h, int w) {
    	int max = 0, cur = matrix[i][j];
    	if (i>0 && matrix[i-1][j] < cur) 
    		max = Math.max(max, mem[i-1][j]!=0 ? mem[i-1][j] : dfs(matrix, mem, i-1, j, h, w));
    	if (j>0 && matrix[i][j-1] < cur) 
    		max = Math.max(max, mem[i][j-1]!=0 ? mem[i][j-1] : dfs(matrix, mem, i, j-1, h, w));
    	if (i<h-1 && matrix[i+1][j] < cur) 
    		max = Math.max(max, mem[i+1][j]!=0 ? mem[i+1][j] : dfs(matrix, mem, i+1, j, h, w));
    	if (j<w-1 && matrix[i][j+1] < cur) 
    		max = Math.max(max, mem[i][j+1]!=0 ? mem[i][j+1] : dfs(matrix, mem, i, j+1, h, w));
    		
    	mem[i][j] = max + 1;
    	return mem[i][j];
    }
    

Log in to reply
 

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