Objective: Given two dimensional matrix, write an algorithm to find out the snake sequence which has the maximum length. There could be many snake sequence in the matrix, you need to return the one with the maximum length. Travel is allowed only in two directions, either go right OR go down.
What is snake sequence: Snake sequence can be made if number in adjacent right cell or number in the adjacent down cell is either +1 or -1 from the number in the current cell.
Example:
Approach:
- This problem is the extension of the problem “Count all paths from top left to bottom right of a mXn matrix” with some extra conditions.
- You can travel only in two directions, either go right or go down.
- All we need to take care if one extra condition that we can travel only to the adjacent cells (right or down) only if number in those cells has difference of 1 from the current cell.
- Have a temporary storage , two dimensional array to store the results of snake result.
- Keep tracking of maximum length and at the end print the sequence using temporary array.
- We will use the Bottom-up approach of Dynamic programming and store the results of sub problems to reuse them in future.
- See the recursive equation and code for better understanding.
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class SnakeSequence { | |
| public int getMaxSequence(int [][] matrix){ | |
| int rows = matrix.length; | |
| int cols = matrix[0].length; | |
| int maxLenth =1; | |
| int maxRow = 0; | |
| int maxCol = 0; | |
| //create result matrix | |
| int [][] result = new int [rows][cols]; | |
| //if no sequence is found then every cell itself is a sequence of length 1 | |
| for (int i = 0; i <rows ; i++) { | |
| for (int j = 0; j <cols ; j++) { | |
| result[i][j] =1; | |
| } | |
| } | |
| for (int i = 0; i <rows ; i++) { | |
| for (int j = 0; j <cols ; j++) { | |
| if(i!=0 || j!=0){ | |
| //check from left | |
| if(i>0 && Math.abs(matrix[i][j]-matrix[i–1][j])==1){ | |
| result[i][j] = Math.max(result[i][j], | |
| result[i–1][j]+1); | |
| if(maxLenth<result[i][j]){ | |
| maxLenth = result[i][j]; | |
| maxRow = i; | |
| maxCol = j; | |
| } | |
| } | |
| //check from top | |
| if(j>0 && Math.abs(matrix[i][j]-matrix[i][j–1])==1){ | |
| result[i][j] = Math.max(result[i][j], | |
| result[i][j–1]+1); | |
| if(maxLenth<result[i][j]){ | |
| maxLenth = result[i][j]; | |
| maxRow = i; | |
| maxCol = j; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| //Now we will check the max entry in the result[][]. | |
| System.out.println("Max Snake Sequence : " + maxLenth); | |
| printPath(matrix, result, maxLenth, maxRow, maxCol); | |
| return 0; | |
| } | |
| public void printPath(int [][] matrix, int [][] result, int maxLength, int maxRow, int maxCol){ | |
| int len = maxLength; | |
| while(maxLength>=1){ | |
| System.out.print(" – " + matrix[maxRow][maxCol]); | |
| if(maxRow>0 && Math.abs(result[maxRow–1][maxCol]-result[maxRow][maxCol])==1 | |
| && Math.abs(matrix[maxRow–1][maxCol]-matrix[maxRow][maxCol])==1){ | |
| maxRow–; | |
| }else if(maxCol>0 && Math.abs(result[maxRow][maxCol–1]-result[maxRow][maxCol])==1 | |
| && Math.abs(matrix[maxRow][maxCol–1]-matrix[maxRow][maxCol])==1){ | |
| maxCol–; | |
| } | |
| maxLength–; | |
| } | |
| } | |
| public static void main(String[] args) { | |
| int arrA [][] = {{1, 2, 1, 2}, | |
| {7, 7, 2, 5}, | |
| {6, 4, 3, 4}, | |
| {1, 2, 2, 5}}; | |
| SnakeSequence snakeSequence = new SnakeSequence(); | |
| snakeSequence.getMaxSequence(arrA); | |
| } | |
| } |
Output:
Max Snake Sequence : 7 - 5 - 4 - 3 - 2 - 1 - 2 - 1
Recursive equation in that table has a typo. It never consider j-1.
if I change the order of “if else” statements in print path function the printed sequence doesn’t match with the expected sequence.
Should we always start checking the row first and then column?
Yes, I agree, this logic alone won’t work in this case. We would have to check the original matrix as well.
Below function should also do that please let me know if you see any issues
To call
Stack longest = new Stack();
findMaxLengthSnake(A,0,0,new Stack(),longest);
System.out.println(longest);
and the function
private static Stack findMaxLengthSnake(int[][] matrix,int row, int column, Stack currentPath,Stack longest) {
if(currentPath.size() > longest.size()){
longest.clear();
longest.addAll(currentPath);
}
if(row==matrix.length || matrix[row].length == column){
return currentPath;
}
int currentValue = matrix[row][column];
if(!currentPath.isEmpty() && Math.abs(currentPath.peek()-currentValue) != 1){
return currentPath;
}
currentPath.push(currentValue);
findMaxLengthSnake(matrix, row, column+1,currentPath,longest);
findMaxLengthSnake(matrix, row+1, column,currentPath,longest);
currentPath.pop();
return currentPath;
}
This algorithm is not entirely right, it is missing the condition of checking for meeting the condition in the original matrix before print. If you run it for the following example you will see that it fails.
int arrA [][] = {{1, 2, 3, 9},
{2, 9, 2, 1},
{3, 9, 9, 2},
{4, 5, 6, 7}};
Max Snake Sequence : 7
– 7 – 2 – 1 – 2 – 3 – 2 – 1