Matrix in Zig-Zag Form

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

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:

• Boundary Traversal of Binary Tree
• Mathematical Puzzles
• Ternary Operator in C
• Logical Puzzles
• Pattern Based Puzzles
• Cross The Bridge
• Measuring Time by Burning Rope
• Multi-dimensional Arrays
• Inverted V using Asterisk Pattern
• Palindrome Pattern
• Matrix in Wave Form
• Web Technologies
• Top 150 Interview Puzzles

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.