Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
[9,9,4],
[6,6,8],
[2,1,1] ] Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
[3,4,5],
[3,2,6],
[2,2,1] ] Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Solve by Backtracking
Ideally, we could check each possible path starting from each possible position in the grid. At each point we have 4 neighbors to walk through. We need to return the maximum length walk among all the walks that goes through 4 neighbors. We will start from a neighbor of (i,j) and backtrack to (i,j) after completion of walk through the neighbor. We will then continue walking to next neighbor.

Now, question is how do we perform the walk and how to make sure that we don’t walk through the same path over and over. This is a classic backtrack problem where we need to do a DFS walk. We will halt the walk through a neighbor if it is not safe i.e. falling out of boundary or not a strictly increasing order path. Each time we perform a walk to a grid position in the path we increase the length of the current path. After we finish a walk we update the max len by using the path length of the current walk.

Ok, we performed the walk through DFS. But how to avoid walking through the same path (or subpath) again and again? Note that, if we already performed a walk starting from grid point(i,j) then any time we come back to the node through a different walk, we can actually skip the walk through (i,j) by caching the result during first walk through this node. That is we can memorize the max length walks using a dp table dp[i][j].

Below is the O(n^2) implementation of the idea described above.

public class Solution {
private static final int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	private int[][] dp;
	
	public int longestIncreasingPath(int[][] matrix) {
	    if(matrix.length == 0){
	        return 0;
	    }
	    if(matrix.length == 1 && matrix[0].length == 1){
	        return matrix[0][0];
	    }
	    
	    //dp table to save max path already computed
	    dp = new int[matrix.length][matrix[0].length];
		int maxLen = 0;
		for(int i = 0; i < matrix.length; i++){
			//try to walk down from wach cell
			for(int j = 0; j< matrix[0].length; j++){
				//walk down from current position	
				int pathLen = 1+walk(matrix, i, j);
				//uodate max length by current walk path len
				maxLen = Math.max(maxLen, pathLen);
			}
		}
		
		return maxLen;
	}
	
	public int walk(int[][] mat, int i, int j){
	    if(dp[i][j] > 0){
	        return dp[i][j];
	    }
	    
		int maxLen = 0;
		
		//wal to all 4 directions
		for(int d = 0; d < dir.length; d++){
			int r = i+dir[d][0];
			int c = j+dir[d][1];
			
			//if not safe or not incerasing then prune this path
			if(!isSafe(mat, r, c) || mat[r][c] <= mat[i][j]){
			    continue;
			}
			
			//other wise do a dfs walk
		    int pathLen = 1+walk(mat, r, c);
		    maxLen = Math.max(maxLen, pathLen);
		}
		
		//update dp table for current position i,j
		dp[i][j] = maxLen;
		return maxLen;
	}
	
	private boolean isSafe(int mat[][], int i, int j){
		if(i >= mat.length || i < 0 || j >= mat[0].length || j < 0){
			return false;
		}
		
		return true;
	}
}