Traverse an array diagonally

 

Question

   How would you traverse an array diagonally and display its contents ?

Say you have something like this,

1  2  3
4  5  6
7  8  9
In the above array, if you traverse from top left corner, then the list of number will be,

[1], [2,4], [3,5,7], [6,8], [9]

How would you get the above set?

Solution

Reference: http://stackoverflow.com/questions/1779199/traverse-matrix-in-diagonal-strips

     0     1     2

0   1     2     3

1    4    5     6

2    7    8     9

The list of indices for the required traversals are,

{[0,0]}  {[0,1][1,0]}  {[0,2][1,1][2,0]}  {[1,2][2,1]} {[2,2]}

If you can get the pattern, then you can do this easily. Total 5 slices will come which is array size N * 2-1. i.e, for 3x3 = 6-1 = 5.

you should have a incrementing counter at row/column when moving to the middle slice. After that you need a decrementing counter at row/column.

Code

void main()

{

    int x[3][3] = {1, 2, 3,

                   4, 5, 6,

                   7, 8, 9};

    int N=3;

    for (int slice = 0; slice < N*2-1; ++slice) {

        int z = slice < N ? 0 : slice - N + 1;

        for (int j = z; j <= slice - z; ++j) {

            int c1=j;

            int c2=(N-1)-(slice-j);

            printf("%d ", x[c1][c2]);

        }

        printf("\n");

    }

    printf("\n");

    for (int slice = 0; slice < N*2-1; ++slice) {

        int z = slice < N ? 0 : slice - N + 1;

        for (int j = z; j <= slice - z; ++j) {

            int c1=j;

            int c2=slice-j;

            printf("%d ", x[c1][c2]);

        }

        printf("\n");

    }

}

• here slice maintains the incrementing/decrementing index required. slice-N+1 will take care of that value
• slice-j allows as move in both row and column.
• When you need to move from top right, just subtract N-1 from slice-j so that you also travel from top right.

Output

Top right to bottom left

3
2 6
1 5 9
4 8
7

Top left to bottom right

1
2 4
3 5 7
6 8
9