Home » Interview coding problems/challenges

Largest zigzag sequence

Largest zigzag sequence: This problem is a standard recursion problem being featured in Directi. Here, we are solving the Largest zigzag sequence using dynamic programming (C++ implementation). Submitted by Radib Kar, on April 19, 2020

Problem statement

Given a square matrix of size n x n, find the sum of the Zigzag sequence with the largest sum. A zigzag sequence starts from the top and ends at the bottom. Two consecutive elements of sequence cannot belong to the same column.

    Input:
    First line contains an integer N denoting the size of the matrix. 
    Then in the next line are N*N space separated values of the matrix.

    Output:
    Print the required max sum.

    Constraints:
    1<=N<=100
    1<=M[][]<=1000

Example

    Input:
    Input matrix
    3 8 2
    4 8 5
    6 9 7
    
    Output: 22
    Maximum Zigzag sequence is: 
    8->5->9
    Other sequences can be: 
    3->8->6 etc.

    Input:
    Input matrix
    3  2  1
    10 8  5 
    6  6  4
    
    Output: 18
    In the above also, the maximum zigzag sequence will be:
    2->10->6

The second example clearly shows that the greedy solution wouldn't work. Let's say we opt for greedy technique and as a measure, what we do is to extract local maximum, i.e., to extract maximum out of this row and the go-ahead to the next row and find out maximum skipping the column where we found our last maximum.

So if we follow a similar approach, let's check what we can lead to.

So, firstly, we will pick 3 out of the first row (0^th row)

From the next row, we will pick 8 as we can't peek 10 due to out constraint.

And from the next row, we will pick 6 (of 0^th column)

So it sums up to 3+8+6 which is 17. But it's wrong we know output would be 18. So finding local best doesn't lead to global best. Hence, greedy will not work here.

We need dynamic programing or recursion to solve.

Solution Approach

So, let's see what can be a recursive solution. Then, we will check for overlapping sub-problems and will gradually optimize the recursion by memorization.

Let the recursive function be, recurZigzag(matrix, cur_row, cur_colulm, n)

    Function recurZigzag(matrix,currow,curcolulm):
        If (currow reaches n)
            Return 0;
        for i=0 to n except curcolumn
            Return  matrix[currow][curcolumn] + max(recurZigzag(matrix, currow + 1, i))
    End Function

    // In the main function
    for column=0 to n-1
    result=max⁡(result,recurZigzag(matrix,0,column)

So what we did?

We are starting from each column on the top row.

Then we are recursively checking for the next row skipping the current column. So, this checks all combinations possible.

I would recommend to create the recursion tree for example 1 and check whether you can find overlapping sub-problems. There will be a lot of overlapping problems even for smaller inputs.

So, we need to pass that overhead and we can solve that by memorization technique where we store the value of solved sub-problem in DP[][]

So, we first lookup in DP[][] whether it's already solved or not. If it's already solved then we will have some value for DP[i][j] (for subproblem, f(i,j)), Else DP[i][j] will contain the initialized value only.

This is the trick here.

Below is the full CPP implementation for understanding memorization.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int findmax(vector<int> arr, int in, int n, int* lastindex)
{
    int max = INT_MIN;
    for (int i = 0; i < n; i++) {
        if (arr[i] > max && i != in) {
            max = arr[i];
            *lastindex = i;
        }
    }
    return max;
}

int recurZigZag(vector<vector<int> > arr, int row, int col, int n, int** dp)
{
    //memoization part
    if (dp[row][col] != -1) //if already solved, no need to compute again
        return dp[row][col];

    if (row == n - 1) {
        dp[row][col] = arr[row][col];
        return arr[row][col];
    }
    int max = INT_MIN;
    for (int k = 0; k < n; k++) {
        if (k != col) {
            int t = recurZigZag(arr, row + 1, k, n, dp);
            if (max < t)
                max = t;
        }
    }
    dp[row][col] = std::max(dp[row][col], arr[row][col] + max); //store solution
    return dp[row][col];
}

int main()
{
    int t, n, item;

    cout << "Enter test case:\n";
    cin >> t;

    for (int i = 0; i < t; i++) {
        cout << "Input size of square matrix\n";
        cin >> n;

        vector<vector<int> > arr;

        cout << "Input the square matrix\n";
        for (int i = 0; i < n; i++) {
            vector<int> inn;
            for (int j = 0; j < n; j++) {
                cin >> item;
                inn.push_back(item);
            }
            arr.push_back(inn);
        }

        int** dp = (int**)(malloc(sizeof(int*) * n));

        for (int i = 0; i < n; i++) {
            dp[i] = (int*)(malloc(sizeof(int) * n));
            for (int j = 0; j < n; j++)
                dp[i][j] = -1;
        }

        int mymax = INT_MIN;

        for (int i = 0; i < n; i++) {
            int p = recurZigZag(arr, 0, i, n, dp);
            if (p > mymax)
                mymax = p;
        }

        cout << "Maximum zigzag sum: " << mymax << endl;
    }

    return 0;
}

Output

Enter test case:
2
Input size of square matrix 
3
Input the square matrix  
3 8 2  
4 8 5  
6 9 7  
Maximum zigzag sum: 22
Input size of square matrix 
3
Input the square matrix  
3 2 1  
10 8 5 
6 6 4  
Maximum zigzag sum: 18