Sum of the diagonal elements in a Spiral Matrix in Javascript

Question

So I have been given an array = [ 1 2 3 8 9 4 7 6 5 ] which is a spiral traversal of a square matrix of size n x n. What I needed to do was to compute the sum of primary and secondary diagonals and print it. I was able to convert this 1D array into a 2D array of size n*n and compute the sum of both diagonals like this:

p.s.: array is something like this [ [1, 2, 3], [6, 5, 8], [7, 4, 9] ]

function spDiag(n,arr){
    let mat = [];
    let primary = 0, secondary = 0;
    while(arr.length) mat.push(arr.splice(0, n));
    
    for(let i = 0; i < n; i++){
        for(let j = 0; j < n; j++){
            if(i === j) primary += mat[i][j];
            
            if((i + j) === (n-1)) secondary += mat[i][j];
        }
        
    }
    console.log(primary + secondary)
    console.log(JSON.stringify(mat));
    
}

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

But the task was to form a spiral matrix and then compute the sum of diagonals and not just a 2D matrix and because of this my output is coming wrong. How can I convert this 1D array to a spiral matrix?

Answer 1

You don't really need to turn the 1D array into a 2D array, nor do you need to visit each value in the array. The diagonals follow an easy pattern, as the index-distance between 2 consecutive elements on a diagonal follows a pattern.

See for instance for a matrix of 7x7 which indexes of the spiral sequence are on a diagonal:

 0  .  .  .  .  .  6
 . 24  .  .  . 28  .
 .  . 40  . 42  .  .
 .  .  . 48  .  .  .
 .  . 46  . 44  .  .
 . 36  .  .  . 32  .
18  .  .  .  .  . 12

The gaps between two consecutive indices that are on the diagonal (in order of index) are: 6, 6, 6, 6, 4, 4, 4, 4, 2, 2, 2, 2. The general pattern for these gaps is: ??1,??1,??1,??1,??3,??3,??3,??3,...etc.

Implementation

As the size of the given array is the square of ?, I don't see why you would need to pass ? as argument. It is redundant information.

So:

function sumDiagonals(arr) {
    let n = Math.sqrt(arr.length);
    if (n % 1) throw "Array size should be perfect square";
    let sum = 0;
    let len = n*2 - n%2; // The number of values on diagonals
    for (let i = 0, j = 0; j < len; i += n - 1 - (j++ >> 2)*2) {
        sum += arr[i];
    }
    return sum;
}

let arr =  [1, 2, 3, 8, 9, 4, 7, 6, 5];
console.log(sumDiagonals(arr));