209. Find longest Snake sequence in a given matrix

Objective: Given a two-dimensional matrix, write an algorithm to find out the snake sequence which has the maximum length. There could be many snake sequences 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: A snake sequence can be made if the number in the adjacent right cell or the number in the adjacent down cell is either +1 or -1 from the number in the current cell.

Example:

Approach:

1. 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.
2. You can travel only in two directions, either go right or go down.
3. All we need to take care of is one extra condition that we can travel only to the adjacent cells (right or down) only if the number in those cells has a difference of 1 from the current cell.
4. Have a temporary storage, two-dimensional array to store the results of the snake result.
5. Keep tracking of maximum length and at the end print the sequence using a temporary array.
6. We will use the Bottom-up approach of Dynamic pro­gram­ming and store the results of sub prob­lems to reuse them in the future.
7. See the recursive equation and code for a better understanding.

Output:

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

Related Problems:

- Dynamic programming – Printer Problem | Leetcode Hard
- Find first two largest elements in a given array Beginner
- Print Stack in reverse order Beginner
- Linear Search vs Binary Search Beginner
- Print all subarrays of a given array Medium