Given 1’s, 2’s, 3’s ……k’s Print them in ZigZag way

Introduction

This blog covers a matrix problem. Matrices are among the most important and often asked data structures in programming contests and technical interviews. There are various standard matrix problems and techniques. This blog tackles a coding task that involves printing a given count of positive integers in a zig-zag pattern.

Must Read, Array Implementation of Queue and Rabin Karp Algorithm

Problem Statement

Ninja is given a number of rows and columns and the number of 1's, 2's, 3's,..... k's that are to be printed. He is challenged with printing them in a zig-zag pattern. It is made sure that n*m (number of rows*columns) equals the number of 1's + 2's + 3's +..... + k's. Can you help him in completing this task?

Sample Examples

Input - 1

2 3
1 2 1 2

Output

Explanation

Here, 
    number of 1's are 1
    number of 2's are 2
    number of 3's are 1
    number of 4's are 2
These are printed in a 2*3 matrix in a zig-zag pattern.

Input - 2

4 5 
1 2 6 3 2 3 3

Output

Explanation

Here, 
    number of 1's are 1
    number of 2's are 2
    number of 3's are 6
    number of 4's are 3
    number of 5's are 2
    number of 6's are 3
    number of 7's are 3
These are printed in a 4*5 matrix in a zig-zag pattern.

Approach

The approach to the above problem is quite intuitive and straightforward. We will go through all the elements of the number array and insert all the numbers from the array of the i-th index into a two-dimensional array until it reaches zero. In the end, we will print out this newly-formed array. The resultant 2-d array will be in zig-zag pattern.

Algorithm

1. Declare a two-dimensional array to store elements in a zig-zag pattern.

2. Start traversing all of the elements of the number array.

3. While traversing, insert all of the integers from the i-th index's array into the two-dimensional array until it reaches zero.

4. Return this two- dimensional array.

Implementation in C++

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

// function for printing a given number of 1's,
// 2's, 3's ....k's in a zig-zag pattern.

void printPattern(int row, int cols, int nums[])
{
    int k = 0;
    // declaring a two-dimensional array to store numbers in a zig-zag pattern.
    int mat[row][cols];

    for (int i = 0; i < row; i++)
    {
        // for even row
        if (i % 2 == 0)
        {
            for (int j = 0; j < cols and nums[k] > 0; j++)
            {
                // storing the element.
                mat[i][j] = k + 1;

                // decrementing element at the kth index.
                nums[k]--;

                // if array contains zero then increments index
                if (nums[k] == 0)
                    k++;
            }
        }

        // for odd row.
        else
        {
            for (int j = cols - 1; j >= 0 and nums[k] > 0; j--)
            {
                // storing element.
                mat[i][j] = k + 1;

                // decrementing element at the kth index.
                nums[k]--;

                // if array contains zero then increments index
                if (nums[k] == 0)
                    k++;
            }
        }
    }

    // printing the array.
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < cols; j++)
            cout << mat[i][j] << " ";

        cout << endl;
    }
}

// Driver code
int main()
{
    int row = 4;
    int cols = 5;
    int nums[] = {1, 2, 6, 3, 2, 3, 3};
    cout << "Number of rows and columns respectively are: " << endl
         << row << " " << cols << endl;
    cout << "The given number array is: " << endl;
    for (size_t i = 0; i < 7; i++)
    {
        cout << nums[i] << " ";
    }

    cout << endl;
    cout << "The desired two-dimensional pattern is: " << endl;
    printPattern(row, cols, nums);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Time Complexity

The time complexity for the given approach is O(m*n) as we traverse the entire matrix to fill up the elements in the n*m matrix and print them in a zig-zag pattern.

Space complexity

The Space Complexity of the above approach turns out to be O(n*m) as we require a matrix of size n*m to store the zig-zag pattern.