CC-13 : Find longest incremental path.

Description:

Given an adjacency matrix, find the length of longest path of incrementing numbers. The path can only travel in directions left, right, up down of cells sharing a boundary but cannot travel diagonal wise.

Test cases and expected outputs:

Input Parameters	Expected outputs
Matrix : 1,2,3, 4,6,7, 9,10,11,	Longest increasing path: 5

Pseudocode:

findLongestIncPath (int[][] matrix) method:

Initialize a variable named lngstIncPath to store the length of longest path found.

Set variable named rows to matrix.length.

Set variable named columns to matrix[0].length.

Initialize a 2 dimensional array called memorised with same dimensions as input matrix.

Iterate through vertices of matrix using a for loop with iIdx as loop variable with values from 0 to count of matrix.length:

Iterate through vertices of matrix using a for loop with jIdx as loop variable with values from 0 to count of matrix[0].length:

Set variable currlngstIncPath to return value from call to longestIncPathDfs (iIdx,jIdx, matrix, memorised, -1).

If currlngstIncPath > lngstIncPath then set lngstIncPath= currlngstIncPath.

Return lngstIncPath.

findIslandPerimeterDfs (int row, int col, int[][] matrix, int[][] memorized, int prevVal) method:

if row and col are within index limits of matric and matrix[row][col]<=prevVal:

return 0.

If visited[row][col]>1, return memorized[row][col].

Initialise lngstIncPath=1.

Set prevVal= matrix[row][col].

Set currlngstIncPath=0.

Set currlngstIncPath int variable to value return by recursive call to longestIncPathDfs (row+1,col, matrix, memorised, prevVal).

If currlngstIncPath > lngstIncPath then set lngstIncPath= currlngstIncPath.

Set currlngstIncPath int variable to value return by recursive call to longestIncPathDfs (row-1,col, matrix, memorised, prevVal).

If currlngstIncPath > lngstIncPath then set lngstIncPath= currlngstIncPath.

Set currlngstIncPath int variable to value return by recursive call to longestIncPathDfs (row,col-1, matrix, memorised, prevVal).

If currlngstIncPath > lngstIncPath then set lngstIncPath= currlngstIncPath.

Return lngstIncPath.

Code:

public int longestIncPathDfs(int row, int col, int[][] matrix, int[][] memorised,int prevVal ){
	if  ((row < 0 ) || (row >= matrix.length)
    || (col < 0 ) ||(col >= matrix[0].length) 
	|| (matrix[row][col] <= prevVal)){
		return 0;
	}
	if (memorised[row][col] > 0) {
		return memorised[row][col];
	}
	int lngstIncPath=1;	
	prevVal=matrix[row][col];
	int currlngstIncPath=0;
	currlngstIncPath=1+longestIncPathDfs(row+1,col,matrix,memorised,prevVal);
	if (currlngstIncPath > lngstIncPath){
		lngstIncPath=currlngstIncPath;
		
	}
	currlngstIncPath=1+longestIncPathDfs(row,col+1,matrix,memorised,prevVal);
	if (currlngstIncPath > lngstIncPath){
		lngstIncPath=currlngstIncPath;
	}
	currlngstIncPath=1+longestIncPathDfs(row-1, col, matrix,memorised,prevVal);
	if (currlngstIncPath > lngstIncPath){
		lngstIncPath=currlngstIncPath;
	}
	currlngstIncPath=1+longestIncPathDfs(row, col-1, matrix,memorised,prevVal);
	if (currlngstIncPath > lngstIncPath){
		lngstIncPath=currlngstIncPath;
	}
	memorised[row][col]=lngstIncPath;
	return lngstIncPath;
}

public int findLongestIncPath(int[][] matrix) {
	int rows=matrix.length;
	int cols=matrix[0].length;
	int [][] memorised=new int[rows][cols];
	int lngstIncPath=0;
	for(int iIdx=0; iIdx < rows; iIdx++){
        for(int jIdx=0; jIdx < cols;jIdx++){
        	int currlngstIncPath=longestIncPathDfs(iIdx,jIdx,matrix,memorised, -1);
        	if (currlngstIncPath > lngstIncPath){
        		lngstIncPath=currlngstIncPath;
        	}
        }
    } 
	return lngstIncPath;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class GraphFindLongestIncPath {

public int longestIncPathDfs(int row, int col, int[][] matrix, int[][] memorised,int prevVal ){
	if  ((row < 0 ) || (row >= matrix.length)
    || (col < 0 ) ||(col >= matrix[0].length) 
	|| (matrix[row][col] <= prevVal)){
		return 0;
	}
	if (memorised[row][col] > 0) {
		return memorised[row][col];
	}
	int lngstIncPath=1;	
	prevVal=matrix[row][col];
	int currlngstIncPath=0;
	currlngstIncPath=1+longestIncPathDfs(row+1,col,matrix,memorised,prevVal);
	if (currlngstIncPath > lngstIncPath){
		lngstIncPath=currlngstIncPath;
		
	}
	currlngstIncPath=1+longestIncPathDfs(row,col+1,matrix,memorised,prevVal);
	if (currlngstIncPath > lngstIncPath){
		lngstIncPath=currlngstIncPath;
	}
	currlngstIncPath=1+longestIncPathDfs(row-1, col, matrix,memorised,prevVal);
	if (currlngstIncPath > lngstIncPath){
		lngstIncPath=currlngstIncPath;
	}
	currlngstIncPath=1+longestIncPathDfs(row, col-1, matrix,memorised,prevVal);
	if (currlngstIncPath > lngstIncPath){
		lngstIncPath=currlngstIncPath;
	}
	memorised[row][col]=lngstIncPath;
	return lngstIncPath;
}

public int findLongestIncPath(int[][] matrix) {
	int rows=matrix.length;
	int cols=matrix[0].length;
	int [][] memorised=new int[rows][cols];
	int lngstIncPath=0;
	for(int iIdx=0; iIdx < rows; iIdx++){
        for(int jIdx=0; jIdx < cols;jIdx++){
        	int currlngstIncPath=longestIncPathDfs(iIdx,jIdx,matrix,memorised, -1);
        	if (currlngstIncPath > lngstIncPath){
        		lngstIncPath=currlngstIncPath;
        	}
        }
    } 
	return lngstIncPath;
}

public static void print2dArray(int[][] intArray, String label) throws Exception {
	// Case 1: The input Array is null !!
    if (intArray == null) { System.out.println("\n\n Input 2d Array was null !! \n"); return; }
    // Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("***********************************************************************");
	System.out.print(label+" : \n");
	int rIdx=0; int cIdx=0;
	for (rIdx=0; rIdx < intArray.length; rIdx++) {
		for (cIdx=0; cIdx < intArray[rIdx].length; cIdx++) {
			System.out.print(intArray[rIdx][cIdx]);
			if (cIdx < intArray[rIdx].length) System.out.print(",");
		}
		System.out.print("\n");
	} 
	System.out.println();
	System.out.println("************************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}

public static void main(String[] args) {

int retVal;
try {
	GraphFindLongestIncPath gph=new GraphFindLongestIncPath();
	int[][] matrix = {	{1,2,3},
						{4,6,7},	
						{9,10,11}};
	print2dArray(matrix, "Matrix" );
	retVal=gph.findLongestIncPath(matrix);
	System.out.println("Longest increasing path: "+ retVal);		
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}

}