Ajay Ajay - 5 months ago 45
PHP Question

Get diagonal values of spiral matrix

I have a n*n spiral matrix.


if N = 4

then matrix :

7 8 9 10
6 1 2 11
5 4 3 12
16 15 14 13


if N = 3

7 8 9
6 1 2
5 4 3



I want to get the diagonal values of this spiral matrix.

In the
n=4
case diagonal values would be 7,1,3,13,10,2,4,16

I can do this by storing this matrix in array and traversing for each diagonal value.

Is there any better way to get these values.

Answer

To get the numbers on the main diagonal, we can notice that the values are

1 = 1
1 + 2 = 3
1 + 2 + 4 = 7
1 + 2 + 4 + 6 = 13

So the general formula is 1 + (sum i = 0 to k of 2*i) for k = 0, 1, 2, ... Simplifying this, we get k^2 + k + 1 for k = 0, 1, 2, ...

In PHP, we can generate these via something like this:

function mainDiagonal($n) {
    $values = array();

    for ($k = 0; $k < $n; $k++) {
        $values[] = $k*$k + $k + 1;
    }

    return $values;
}

To get the numbers on the antidiagonal for even N we see:

2 = 2
2 + 2 = 4
2 + 2 + 6 = 10
2 + 2 + 6 + 6 = 16

If we continue this pattern for larger matrices we see the general formula is

sum i = 0 to k of floor(i/2)*4 + 2 for k = 0, 1, 2, ...

Similarly for odd N we find the formula is

1 + (sum i = 0 to k of ceil(i/2)*4) for k = 0, 1, 2, ...

In PHP, we can generate these via something like this:

function antiDiagonal($n) {
    $values = array();

    if ($n % 2 == 0) {
        for ($k = 0; $k < $n; $k++) {
            $accum = 0;

            for ($j = 0; $j <= $k; $j++) {
                $accum += floor($j/2)*4 + 2;
            }

            $values[] = $accum;
        }
    } else {
        for ($k = 0; $k < $n; $k++) {
            $accum = 1;

            for ($j = 0; $j <= $k; $j++) {
                $accum += ceil($j/2)*4;
            }

            $values[] = $accum;
        }
    }

    return $values;
}

Notice that the maximum value of k is one less than the dimension of the matrix.

Combining these functions, we obtain:

array_unique(array_merge(mainDiagonal($n), antiDiagonal($n)))