The problem “Find maximum length Snake sequence” states that we are provided with a grid containing integers. The task is to find a snake sequence with the maximum length. A sequence having adjacent numbers in the grid with an absolute difference of 1, is known as a Snake sequence. Adjacent elements for a number are the numbers which are it’s left and above neighbors, given that they exist inside the grid. Formally speaking, if you are standing at (i,j) cell in the grid then the cells (i, j-1), (i-1, j) are adjacent to it given that they lie inside the grid.
Table of Contents
Example
3 3// dimensions of grid 1 2 3 2 4 5 1 2 1
Maximum length of the Snake Sequence is: 5 The maximum length snake sequence is: 1 2 1 2 1
Explanation
Approach
The problem asks to find the snake sequence with the maximum length and we are provided with a grid as an input. A naive or brute force approach is to start from the top left corner of the grid, and using recursion goes through its right and bottom neighbor. Similarly from those cells go to their neighbors and so on until you find a cell such that moving forward is not an option because of the conditions imposed. Using recursion where in general we have four recursive calls, the time complexity is going to be on the higher side.
Instead of the above approach, we can go with Dynamic Programming because we describe the problem using a recursive solution. Then simply memoizing it to optimize the solution. The time complexity for the above approach was exponential but using dynamic programming can reduce it to polynomial. For this problem, we will be looking at two states first is the row index and then the column index. Each cell in the DP table will be dependent on its just above and just left cell. If we also needed the cells which are being chosen for the answer, we traverse over the DP table and as per the result for each cell. We decide which cell has been picked up to form the sequence.
Code
C++ code to Find maximum length Snake sequence
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n=3, m=3;
int grid[n][m] =
{
{1, 2, 3},
{2, 4, 5},
{1, 2, 1}
};
int dp[n][m];
int mx = 0, en_i = -1, en_j = -1;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
dp[i][j] = 1;
if(i>0 && abs(grid[i-1][j]-grid[i][j]) == 1)
dp[i][j] = max(dp[i-1][j]+1, dp[i][j]);
if(j>0 && abs(grid[i][j-1]-grid[i][j]) == 1)
dp[i][j] = max(dp[i][j-1]+1, dp[i][j]);
if(dp[i][j] > mx){
mx = dp[i][j];
en_i = i;
en_j = j;
}
}
}
cout<<"Maximum length of the Snake Sequence is: "<<mx<<endl;
cout<<"The maximum length snake sequence is: ";
int l_i = -1, l_j = -1;
while(en_i != l_i || en_j != l_j){
cout<<grid[en_i][en_j]<<" ";
l_i = en_i, l_j = en_j;
if(en_i > 0 && dp[en_i][en_j] == dp[en_i-1][en_j] + 1)
en_i--;
else if(en_j > 0 && dp[en_i][en_j] == dp[en_i][en_j-1] + 1)
en_j--;
}
}
Maximum length of the Snake Sequence is: 5 The maximum length snake sequence is: 1 2 1 2 1
Java code to Find maximum length Snake sequence
import java.util.*;
class Main{
public static void main(String[] args)
{
int n=3, m=3;
int grid[][] =
{
{1, 2, 3},
{2, 4, 5},
{1, 2, 1}
};
int dp[][] = new int[n][m];
int mx = 0, en_i = -1, en_j = -1;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
dp[i][j] = 1;
if(i>0 && Math.abs(grid[i-1][j]-grid[i][j]) == 1)
dp[i][j] = Math.max(dp[i-1][j]+1, dp[i][j]);
if(j>0 && Math.abs(grid[i][j-1]-grid[i][j]) == 1)
dp[i][j] = Math.max(dp[i][j-1]+1, dp[i][j]);
if(dp[i][j] > mx){
mx = dp[i][j];
en_i = i;
en_j = j;
}
}
}
System.out.println("Maximum length of the Snake Sequence is: "+mx);
System.out.print("The maximum length snake sequence is: ");
int l_i = -1, l_j = -1;
while(en_i != l_i || en_j != l_j){
System.out.print(grid[en_i][en_j]+" ");
l_i = en_i; l_j = en_j;
if(en_i > 0 && dp[en_i][en_j] == dp[en_i-1][en_j] + 1)
en_i--;
else if(en_j > 0 && dp[en_i][en_j] == dp[en_i][en_j-1] + 1)
en_j--;
}
}
}Maximum length of the Snake Sequence is: 5 The maximum length snake sequence is: 1 2 1 2 1
Complexity Analysis
Time Complexity
O(N*M), where N and M are the number of rows and columns respectively. The time complexity is dependent on the size of the grid. Because that is required for calculating the number of cells in the grid. Thus in the worst-case scenario, we are required to travel the whole grid.
Space Complexity
O(N*M), because we create the DP grid of the same size as that of the input grid.