Print Like A Wave

Easy
0/40
Average time to solve is 20m
235 upvotes
Asked in companies
LenskartAmazonMercer Mettl

Problem statement

For a given two-dimensional integer array/list ‘ARR’ of size (N x M), print the ‘ARR’ in a sine wave order, i.e., print the first column top to bottom, next column bottom to top, and so on.

For eg:-

The sine wave for the matrix:-
1 2
3 4
will be [1, 3, 4, 2].
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line contains an Integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains two integer values, 'N' and 'M,’ separated by a single space. They represent the 'rows' and 'columns,’ respectively, for the two-dimensional array/list ‘ARR’.

The next ‘N’ line contains an ‘M’ single-separated integer denoting the value of ‘ARR’.
Output format : 
For each test case, print the two-dimensional array/list ‘ARR’ elements in the sine wave order in a single line, separated by a single space.

Output for every test case will be printed in a separate line.
Constraints : 
1 <= T <= 10
1 <= N <= 100
1 <= M <= 100
0 <= ARR[i][j] <= 100

Time Limit: 1sec
Sample Input 1:
2
3 4
1 2 3 4
5 6 7 8
9 10 11 12
4 4
1 2 4 5
3 6 8 10
11 12 13 15
16 14 9 7
Sample Output 1:
1 5 9 10 6 2 3 7 11 12 8 4
1 3 11 16 14 12 6 2 4 8 13 9 7 15 10 5
Explanation For Sample Input 1:
Here, the elements are printed in a form of a wave, first, the 0th column is printed from top to bottom then the 1st column from bottom to top, and so on. Basically, the even column is printed from top to bottom and the odd column in the opposite direction.
Sample Input 2:
2
1 1
3
1 2
6 5
Sample Output 2:
3
6 5
Hint

Can we iterate over the matrix to get our order?

Approaches (1)
Brute Force

The basic idea of this approach is to print the elements row-wise. The elements are printed in two ways; top-down and bottom-up. It has been observed that the odd rows are printed in a bottom-up manner, and even ones are printed in a top-down manner. We will use two loops, the first loop will iterate through the number of columns, and the second loop will print the element row-wise.

 

Here is the algorithm:

 

  1. Run a loop from ‘I’ = 0 to ‘M_COL’ (Number of columns given)
    • If the current row is even, then the elements will be printed from top to bottom.
      • Run an inner loop from ‘J’ = 0 to ‘N_ROW’ (Number of rows given)
        • Print all the elements.
    • Else if the current row is odd, then the elements will be printed from bottom to top.
      • Run another loop from ‘J’ = ‘N_ROWS - 1’ to 0.
        • Print all the elements.
Time Complexity

O(N * M), where N is the number of rows and M is the number of columns.

 

Because we are iterating to every element of the given matrix, as N * M elements present in the matrix, the time complexity is O(N * M).

Space Complexity

O(M*N), where N is the number of rows and M is the number of columns.

 

Because we are storing all the elements in a vector, as the total number of elements in the given matrix is M*N, hence the space complexity is O(M*N).

Code Solution
(100% EXP penalty)
Print Like A Wave
Full screen
Console