Zig-Zag of Matrix

Hard
0/120
Average time to solve is 40m
profile
Contributed by
6 upvotes
Asked in companies
Goldman SachsMicrosoftVMware Inc

Problem statement

You are given a matrix ‘mat’ of ‘N’ rows and ‘M’ columns. Your task is to return the Zig-Zag order of the matrix.

The Zig-Zag order of a 5 x 5 matrix is given below

zigZag

For example: 
You are a given the matrix -: 
    ‘mat’ = [[1, 2, 3], 
            [4, 5, 6], 
            [7, 8, 9]]
Here the Zig-Zag order of the given matrix is [1, 2, 4, 7, 5, 3, 6, 8, 9]. Hence the answer is [1, 2, 4, 7, 5, 3, 6, 8, 9].
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, representing the number of rows and columns of the matrix.

The next ‘N’ lines contain ‘M’ space-separated integers denoting the elements of the matrix ‘mat.’
Output Format: 
For each test case, print N*M space-separated integers representing the Zig-Zag order of the matrix.

Print a separate line for each test case.
Constraints: 
1 <= T <= 10
1 <= N, M <= 10^3
0 <= mat[i][j] <= 10^9

Time Limit: 1 sec
Note: 
You do not need to print anything. It has already been taken care of. Just implement the function.
Sample Input 1:
2
3 3
1 2 3
4 5 6
7 8 9
2 3
4 5 6
1 2 3
Sample Output 1:
1 2 4 7 5 3 6 8 9
4 5 1 2 6 3
Explanation:
For the first test cases you are given, 
   ‘mat’ = [[1, 2, 3], 
            [4, 5, 6], 
            [7, 8, 9]]
Here the zigzag order of the given matrix is [1, 2, 4, 7, 5, 3, 6, 8, 9]. Hence the answer is [1, 2, 4, 7, 5, 3, 6, 8, 9].

For the second test cases you are given, 
     ‘mat’ = [[4, 5, 6], 
              [1, 2, 3]]
Here the zigzag order of the given matrix is [4, 5, 1, 2, 6, 3]. Hence the answer is [4, 5, 1, 2, 6, 3].
Sample Input 2:
2
4 4
7 6 0 2
8 4 6 5
3 4 0 4 
5 4 6 3
4 2
0 5
1 4
2 6
9 4
Sample Output 2:
7 6 8 3 4 0 2 6 4 5 4 0 5 4 6 3
0 5 1 2 4 6 9 4
Hint

Try to traverse the matrix according to the question.

Approaches (1)
Iterative Approach

In this approach, we traverse the given matrix diagonally and change the direction when we reach the corner of the matrix.

Each time we change the direction of the path, we will add a new diagonal path to the answer.

 

Algorithm:

  • Initialise a 2D array diagonals of size n + m - 1
  • Iterate i from 0 to n - 1
    • Iterate j from 0 to m - 1
      • Set sum as i + j
      • If sum is not divisible by 2
        • Insert mat[i][j] into the array diagonals[sum]
      • Otherwise,
        • Insert mat[i][j] into the front of the array diagonals[sum]
  • Initialize an empty array ans
  • Iterate diag through diagonals
    • Iterate i through diagonals
      • Insert i into ans 
  • Finally, return ans
Time Complexity

O(N*M), Where N and M are the numbers of rows and columns of the matrix.

 

We are traversing through each element of the array, which will cost O(N*M) time. Hence the final time complexity is O(N*M).

Space Complexity

O(N*M), Where N and M are the numbers of rows and columns of the matrix

 

We are maintaining an array to store the Zig-Zag path of the matrix that will have all the elements of the matrix. Hence the final space complexity is O(N*M).

Code Solution
(100% EXP penalty)
Zig-Zag of Matrix
Full screen
Console