# Find longest Snake sequence in a given matrix

Objec­tive: Given two dimen­sional matrix, write an algo­rithm to find out the snake sequence which has the max­i­mum length. There could be many snake sequence in the matrix, you need to return the one with the max­i­mum length. Travel is allowed only in two direc­tions, either go right OR go down.

What is snake sequence: Snake sequence can be made if num­ber in adja­cent right cell or num­ber in the adja­cent down cell is either +1 or –1 from the num­ber in the cur­rent cell.

Exam­ple:

Approach:

• This prob­lem is the exten­sion of the prob­lem “Count all paths from top left to bot­tom right of a mXn matrix” with some extra conditions.
• You can travel only in two direc­tions, either go right or go down.
• All we need to take care if one extra con­di­tion that we can travel only to the adja­cent cells (right or down) only if num­ber in those cells has dif­fer­ence of 1 from the cur­rent cell.
• Have a tem­po­rary stor­age , two dimen­sional array to store the results of snake result.
• Keep track­ing of max­i­mum length and at the end print the sequence using tem­po­rary array.
• We will use the Bottom-up approach of Dynamic pro­gram­ming and store the results of sub prob­lems to reuse them in future.
• See the recur­sive equa­tion and code for bet­ter understanding.

Code:

Out­put:

```Max Snake Sequence : 7
- 5 - 4 - 3 - 2 - 1 - 2 - 1
```

#### You may also like...

• dogbert82

Recur­sive equa­tion in that table has a typo. It never con­sider j-1.

• Chan­dra Gopalaiah

if I change the order of “if else” state­ments in print path func­tion the printed sequence doesn’t match with the expected sequence.

Should we always start check­ing the row first and then column?

• Shilpi

Yes, I agree, this logic alone won’t work in this case. We would have to check the orig­i­nal matrix as well.

• fatih tekin

Below func­tion 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 func­tion
``` 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; } ```

• Vida Tah­masebi

This algo­rithm is not entirely right, it is miss­ing the con­di­tion of check­ing for meet­ing the con­di­tion in the orig­i­nal matrix before print. If you run it for the fol­low­ing exam­ple 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