Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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:

Snake Sequence (1)

 

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.

Recursive Equation- Snake Sequence

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;
    }