This post is completed by 2 users

  • 0
 Add to List
Medium

413. ZigZag OR Diagonal traversal in 2d array/Matrix using queue

Objective: Given a two-dimensional array or matrix, Write an algorithm to print the given matrix in a zigzag manner or in other words print all the diagonals of the matrix.

Example:

int [][] grid = new int[][] {
           {1, 2, 3, 4},
           {5, 6, 7, 8},
           {9, 10, 11, 12},
           {13, 14, 15, 16}}
Output: 
Zig-Zag Traversal: 
1 
5 2 
9 6 3 
13 10 7 4 
14 11 8 
15 12 
16 

Approach - Use Queue

There are multiple ways this problem can be solved. Earlier we had solved this problem - Print all diagonals of matrix | Set 1 In this post, we will discuss solving this in a simple and straightforward manner by using a queue. 

If you observe the zigzag or diagonal pattern then you will notice that from elements of one diagonal if you move either down or move right you will get the elements of the next diagonal path. So the idea is to keep storing the next level diagonal elements in the queue while printing the current diagonal elements. 

  1. Start the process with the first element in the matrix at index 0,0. Add it to the queue.
  2. Now while the queue is not empty.
    1. Get the size of the queue (this size will tell the number of elements at this diagonal). Run the loop for this size, take the element out from the queue, print it and add the down element and right element to the queue. (handle the edge cases and make sure that duplicates are not added to the queue.). Put a line break for the next level. 

See the image below for better understanding.

Output:

Zig-Zag Traversal: 
1 
5 2 
9 6 3 
13 10 7 4 
14 11 8 
15 12 
16 

Related Problems: