Row Wave Form

Easy
0/40
Average time to solve is 15m
profile
Contributed by
19 upvotes
Asked in companies
AmazonVir SoftechCvent

Problem statement

You are given a 2D array with dimensions ‘N*M’. You need to read the array elements row-wise and return a linear array that stores the elements like a wave i.e the 1st-row elements are stored from left to right, 2nd-row elements are stored from right to left, and so on.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer 'T' representing the number of the test cases. Then ‘T' test cases follow.

The first line of each test case contains two space-separated integers, 'N', 'M', the dimensions of the 2D array. 

The next ‘N’ lines consist of ‘M’ space-separated integers denoting the array elements.
Output Format: 
For each test case, return a 1D array storing the input array elements like a wave.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= ‘T’ <= 10
1 <= 'N', ‘M’ <= 10^3
1 <= ‘ARR[i][j]’ <= 10^5

Where ARR[i][j] is the array element in the ith row of the jth column.

Time limit: 1 second
Sample Input 1:
2
2 2 
1 2
0 5
2 3
5 1 2
7 0 1
Sample Output 1:
1 2 5 0
5 1 2 1 0 7
Explanation of Input 1:
For test case 1, the array is traversed as:
The first row is traversed from left to right. -> [1, 2]
The second row is traversed from right to left. -> [5, 0]
Therefore the final answer is [1, 2, 5, 0].

For test case 2, the array is traversed as:
First row is traversed from left to right. -> [5, 1, 2]
Second row is traversed from right to left. -> [1, 0, 7]
Therefore the final answer is [5, 1, 2, 1, 0, 7]
Sample Input 2:
1
3 3
0 1 1
8 0 9
5 4 1
Sample Output 2
0 1 1 9 0 8 5 4 1
Explanation of Input 1:
For test case 1, the array is traversed as:
The first row is traversed from left to right. -> [0, 1, 1]
The second row is traversed from right to left. -> [9, 0, 8]
The third row is traversed from left to right -> [5, 4, 1]
Therefore the final answer is [0, 1, 1, 9, 0, 8, 5, 4, 1]
Hint

Try to find a brute force approach.

Approaches (1)
Brute Force Approach:

We can observe that considering 1 based indexing, the rows having odd index need to be read from left to right, and the rows having index even are read from right to left. Therefore for all the rows we can check this condition and insert the elements in a linear array ANS.

 

Steps:

  • Keep a linear array ANS[] which will store our answer.
  • Traverse the rows of the 2D array. Let i be the current row. (1 <= i <= N)
    • If i is odd
      • We need to traverse this row from j = 1 to M where j denotes the column number.
    • If i is even
      • We need to traverse this row from j = M to 1 where j denotes the column number.

Return the array ANS.

Time Complexity

O(N*M), where N and M are the rows and columns of the input array respectively.
 

As we traverse the matrix of size ‘N*M’ only a single time. Therefore the net time complexity is O(N*M).

Space Complexity

O(N*M), where N and M are the rows and columns of the input array respectively.


We insert all the elements i.e N*M elements into our 1D array ANS. Therefore the net space complexity is O(N*M).

Code Solution
(100% EXP penalty)
Row Wave Form
Full screen
Console