## Friday, 29 April 2011

### Traverse an array diagonally

Question

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

Say you have something like this,

``1  2  34  5  67  8  9``In the above array, if you traverse from top left corner, then the list of number will be,``
``, [2,4], [3,5,7], [6,8], ``
``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 = {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

`` ``
`` ``