1.
Introduction
2.
Problem statement
3.
Approach
4.
Code
4.1.
C
4.2.
C++
4.3.
Java
4.4.
Python
4.5.
Complexity Analysis
5.
5.1.
What are the two most common ways of traversing a matrix?
5.2.
What are the applications of multidimensional arrays?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Matrix in Zig-Zag Form

Yashesvinee V
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Matrices are 2-D arrays in which elements are known to be arranged in rows and columns. In other words, it is a grid that is used to store data in a structured format. A matrix can be traversed in many ways due to its structure. In this blog, we shall learn the zig-zag traversal of a given matrix.

Problem statement

For a given square matrix, print its elements in the order of a zig-zag traversal, as shown below.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

1. Move one step to the Right. If you can not move Right, move one step Down.

2. Move down diagonally towards the left until you cannot move.

3. Move one step Down. If you canâ€™t, then move one step to the Right.

4. 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;
}``````

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;
}``````

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]+" ");
}
}``````

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=' ')``````

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.

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