Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
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

Author Yashesvinee V
2 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Interview Puzzles

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.

Illustration Image

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.

Illustration Image

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. 

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.

Previous article
Matrix in Wave Form
Next article
Palindrome Pattern
Live masterclass