## 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.