Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Time Complexity
2.2.2.
Space complexity
3.
Frequently Asked Questions
3.1.
Why are heaps used for implementing Priority Queue?
3.2.
How does a deque represent memory?
3.3.
What is a void pointer in C++?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

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

Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

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;
}

 

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

Why are heaps used for implementing Priority Queue?

Heaps are ideal for building a priority queue because of the biggest and smallest element at the root of the tree for a max-heap and a min-heap, respectively.

How does a deque represent memory?

A deque is implemented in computer memory using either a circular array or a circular doubly linked list.

What is a void pointer in C++?

In C, a void pointer is a pointer that has no data type associated with it. It denotes a data location in the storage.

Conclusion

This article extensively discussed the problem of printing a given number of 1’s,2’s,3’s ….k’s in a zig-zag pattern in a 2-d matrix and its time and space complexities.

We hope this blog has helped you enhance your knowledge regarding matrices. After reading about the matrices, are you not feeling excited to read/explore more articles on this topic? Don't worry, Coding Ninjas has you covered. To learn, see Greedy AlgorithmsPair SumSum or ProductSet Matrix zeros and Maximum Subarray Sum.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and much more! If you want to test your competency in coding, you may check out the mock test series and take part in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you can also look at the problems, interview experiences, and interview bundle for placement preparations.

Also, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

 

Happy Learning!

Live masterclass