Largest Zigzag Sequence

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
0 upvote
Asked in companies
DirectiAmazonWells Fargo

Problem statement

You are given a matrix ‘MAT’ of dimensions ‘N x N’. Let’s define a sequence to be ‘zigzag’ if it starts from the top and ends at the bottom such that no two consecutive elements of the sequence belong to the same column.

Your task is to find the sum of the zigzag sequence with the largest sum.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains a single positive integer, ‘N’, as described in the problem statement.

The next ‘N’ lines of each test case contains ‘N’ space-separated number, ‘MAT[i][j]’, representing the value at index (i,j) of the matrix.

Output Format :

For each test case, print the “sum of the zigzag sequence with the largest sum”, as described in the problem statement.

Output for each test case will be printed in a separate line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 100
1 <= MAT[i][j] <= 1000

Where 'MAT[i][j]' denotes the value of matrix at 'jth' column of 'ith' row.

Time Limit: 1sec

Sample Input 1 :

1
2
1 3
2 4

Sample Output 1 :

5
Explanation for sample input 1 :
There are only two possible zigzag sequences:
(i) 1 -> 4 with sum eqaul to 5.
(ii) 3 -> 2 with sum equal to 5.
Hence both are optimal zigzag sequences with a sum equal to 5.

Sample Input 2 :

1
3
1 2 3
3 4 5
4 5 6

Sample Output 2 :

13
Explanation for sample input 2 :
The optimal zigzag sequence is 3 -> 4 -> 6 with a sum eqaul to 13.
Hint

Try to find all possible zigzag sequences using recursion.

Approaches (2)
Recursive Based Approach
  • The idea here is to find all possible zigzag sequences with the help of recursion.
  • Let say we are currently at (i, j). Now we want to move to the (i+1)th row. We can go to any column that means we have total N options available in that row.
  • By the definition of zigzag sequence, no two consecutive elements belong to the same column. In other words, if we are at (i, j) we can go to (i+1, k) provided k != j.
  • At each iteration, we keep track of the maximum value of that function call.
  • The base condition of this recursive function is when i == N-1 (i.e., the last row). So, we just return the matrix entry at (i, j).
Time Complexity

O(N^N), where N is the number of rows and columns in the matrix.

 

We are using the recursion for forming all possible zigzag sequences. As in each function call, we have ‘N’ options available. Hence, the time complexity will be O(N^N).

Space Complexity

O(1).

 

As we are only using the constant extra space.

Code Solution
(100% EXP penalty)
Largest Zigzag Sequence
Full screen
Console