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

if Give Matrix is

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

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.




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