Approach
There are many ways to approach and solve this problem. One of the ways is to traverse the matrix diagonally in a direction until it can not go any further. At that point, change the direction to move one step right or one step down according to the current position of traversal. The code executes in the following sequence.
-
Move one step to the Right. If you can not move Right, move one step Down.
-
Move down diagonally towards the left until you cannot move.
-
Move one step Down. If you can’t, then move one step to the Right.
-
Move Up diagonally towards the Right as far as possible.
At the end of these 4 steps, we would be at (0,2). In order to traverse the remaining elements, follow the above steps in the order 3 → 2 → 1.

Code
The code shown below follows the steps mentioned before. In order to understand how it actually works during execution, simulate the code here.
C
#include<stdio.h>
int main()
{
int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int M = 3, N = 3;
int result[M*N];
result[0] = matrix[0][0]; //Initialization start position
int i=0, j=0, k=1;
while(k < N*M)
{
//move up-right first
while(i>=1&&j<N-1){
i--;
j++;
result[k++] = matrix[i][j];
}
//when we can't move up-right ,then move right one step
if(j<N-1){
j++;
result[k++] = matrix[i][j];
}
//if we can't move right,just move down one step
else if(i<M-1) {
i++;
result[k++] = matrix[i][j];
}
//After that,we will move down-left until it can't move
while(i<M-1&&j>=1) {
i++;
j--;
result[k++] = matrix[i][j];
}
//if we can't move down-left,then move down
if(i<M-1){
i++;
result[k++] = matrix[i][j];
}
//if we can't move down,just move right
else if(j<N-1){
j++;
result[k++] = matrix[i][j];
}
}
for (int i=0; i<M*N; i++)
printf("%d ",result[i]) ;
return 0;
}

You can also try this code with Online C Compiler
Run Code
Output:
1 2 4 7 5 3 6 8 9
C++
#include<iostream>
using namespace std;
int main()
{
int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int M = 3, N = 3;
int result[M*N];
result[0] = matrix[0][0]; //Initialization start position
int i=0, j=0, k=1;
while(k < N*M)
{
//move up-right first
while(i>=1&&j<N-1){
i--;
j++;
result[k++] = matrix[i][j];
}
//when we can't move up-right ,then move right one step
if(j<N-1){
j++;
result[k++] = matrix[i][j];
}
//if we can't move right,just move down one step
else if(i<M-1) {
i++;
result[k++] = matrix[i][j];
}
//After that,we will move down-left until it can't move
while(i<M-1&&j>=1) {
i++;
j--;
result[k++] = matrix[i][j];
}
//if we can't move down-left,then move down
if(i<M-1){
i++;
result[k++] = matrix[i][j];
}
//if we can't move down,just move right
else if(j<N-1){
j++;
result[k++] = matrix[i][j];
}
}
for (int i=0; i<M*N; i++)
cout<<result[i]<< " " ;
return 0;
}

You can also try this code with Online C++ Compiler
Run Code
Output:
1 2 4 7 5 3 6 8 9
Java
public class Main {
public static int[] findOrder(int[][] matrix)
{
if(matrix == null || matrix.length == 0)
return new int[0];
int M = matrix.length, N = matrix[0].length;
int[] result = new int[M*N];
result[0] = matrix[0][0]; //Initialization start position
int i=0, j=0, k=1;
while(k < N*M)
{
//move up-right first
while(i>=1&&j<N-1){
i--;
j++;
result[k++] = matrix[i][j];
}
//when we can't move up-right ,then move right one step
if(j<N-1){
j++;
result[k++] = matrix[i][j];
}
//if we can't move right,just move down one step
else if(i<M-1) {
i++;
result[k++] = matrix[i][j];
}
//After that,we will move down-left until it can't move
while(i<M-1&&j>=1) {
i++;
j--;
result[k++] = matrix[i][j];
}
//if we can't move down-left,then move down
if(i<M-1){
i++;
result[k++] = matrix[i][j];
}
//if we can't move down,just move right
else if(j<N-1){
j++;
result[k++] = matrix[i][j];
}
}
return result;
}
public static void main(String[] args)
{
int arr[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int ans[] = findOrder(arr);
for (int i=0; i<ans.length; i++)
System.out.print(ans[i]+" ");
}
}

You can also try this code with Online Java Compiler
Run Code
Output:
1 2 4 7 5 3 6 8 9
Python
def findOrder(matrix):
result=[0]*(n*m)
result[0] = matrix[0][0]
k=1
i=j=0
while(k<n*m):
while i>=1 and j<n-1:
i-=1
j+=1
result[k] = matrix[i][j]
k+=1
if j<n-1:
j+=1
result[k] = matrix[i][j]
k+=1
elif i<m-1:
i+=1
result[k] = matrix[i][j]
k+=1
while i<m-1 and j>=1:
i+=1
j-=1
result[k] = matrix[i][j]
k+=1
if i<m-1:
i+=1;
result[k] = matrix[i][j]
k+=1
elif j<n-1:
j+=1
result[k] = matrix[i][j]
k+=1
return result
arr=[[1,2,3],[4,5,6],[7,8,9]]
n=m=3
ans=findOrder(arr)
for num in ans:
print(num, end=' ')

You can also try this code with Online Python Compiler
Run Code
Output:
1 2 4 7 5 3 6 8 9
Complexity Analysis
-
Time Complexity: O(N x M)
-
O(N x M) since we process each matrix element exactly once. N is the number of rows, and M is the number of columns.
-
Space Complexity: O(1)
- We do not use any additional data structure. Note that the space occupied by the output array doesn't count towards the space complexity as it is a requirement of the problem itself. Space complexity only includes any additional space we may have used to build the final array.
Frequently Asked Questions
What are the two most common ways of traversing a matrix?
Two common ways of traversing a matrix are row-major-order and column-major-order. The time complexity is O(n x m). Row Major Order, when the matrix is accessed row by row. Column Major Order, when the matrix is accessed column by column.
What are the applications of multidimensional arrays?
Multidimensional arrays are used to store the data in a tabular form. they also have applications in many standard algorithmic problems like Matrix Multiplication, Adjacency matrix representation of graphs and Grid search problems.
Conclusion
This article extensively discusses how to print a matrix in a zig-zag fashion. We hope that this blog has helped you enhance your knowledge about a different ways of traversing a given matrix. If you would like to learn more, check out our articles on the Coding Ninjas Library.
Recommended Readings:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.