Thursday, October 7, 2010

Print a Matrix in diagonal zig zag order

Problem:
Given a square matrix, write a program to print the items in zig zag diagonal order.

Following is an example,

So the output expected for the above example is,

1 -> 2 -> 6 -> 3 -> 7 -> 11 -> 4 -> 8 -> 12 -> 16 -> 5 -> 9 -> 13 -> 17 -> 21 -> 10 -> 14 -> 18 -> 22 -> 15 -> 19 -> 23 -> 20 -> 24 -> 25

Solution:

This program is a bit tricky and is very hard to solve immediately when asked in an interview. People who try to attack problems involving matrices always think they need at least two loops to arrive at the solution. But the surprise here is the problem can be solved in just a single loop with a very simple logic. I have provided the solution in C++ below, you may also try to solve the same in the language of your choice!!

#include <iostream>
using namespace std;

#define MAX 5

int main(){
    int a[MAX][MAX] = 
        {{ 1, 2, 3, 4, 5},
         { 6, 7, 8, 9,10},
         {11,12,13,14,15},
         {16,17,18,19,20},
         {21,22,23,24,25}};
    int i=0,j=0;
    while(i<MAX){
         cout << a[i][j] << " -> ";
         if(i==MAX-1){
             i = j+1; j = MAX-1;
         }
         else if(j==0){
             j = i+1; i = 0;
         }
         else{
             i++; j--;
         }
    }
    cout << endl;
     
    return 0;
}

Cheers!!
Jack

6 comments:

Shashank Mani said...

well You write the program very intelligently but u didn't write it for general 2d matrix e.g your program doesn't work when matrix is not the square matrix e.g. what happens when M!=N which is not d square matrix

b said...

@shashank Mani: Dude.. Read the problem statement again. It clearly says SQUARE matrix

KK123 said...
This comment has been removed by the author.
Rahul Tiwari said...

plz edit the code for the case -
row != col .....

vinny said...

i am communion with b....shashank u should read the problem again.

arpit tak said...

yah its works.. nice wrk man.
can u also tell how to print a spiral matrix of same square.