You are given a square matrix of size N times N. Calculate the absolute difference of the sums across the two main diagonals

Question

This was the question from hackerrack.com,

Explanation of the question

I solved the problem, but I am unable to find the optimistic solution, Can we do using object literals and come across optimal solution?

function getTwoDimention(input){
    var input = input.split('\n');
    var twoDimArr=[];
    for(var n=0; n<input.length; n++){ 
        var subarr = input[n].split(' ');
       if(subarr.length > 1){
           twoDimArr.push(subarr)
       }
    }
    return twoDimArr;
}

function getFristDiagonal(twoDimArr){
    var sum = 0;
    for(var i=0; i<twoDimArr.length; i++){
        for(var j=i; j<=i; j++){
           sum += parseFloat(twoDimArr[i][j]);
        }
    }
    return sum;
}
function getSecondDiagonal(twoDimArr){
    var sum = 0;j=twoDimArr.length-1;
    for(var i=0; i<twoDimArr.length; i++){

           sum += parseFloat(twoDimArr[i][j--]);
    }
    return sum;
}
function processData(input) {
    //Enter your code here
    twoDimArr = getTwoDimention(input);
    var firtDia = getFristDiagonal(twoDimArr);
    var secDia = getSecondDiagonal(twoDimArr);

    console.log(secDia - firtDia);

} 

The actual working code is in jsfiddle

Fiddle Demo

And also for some test case it is failing, when the number of elements vary on each row

Many thanks in advance

Answer 1

I think you mean the optimized solution.

Right now, you are iterating over the array 3 times, once to pull in your data (which takes more memory), and then twice to calculate each diagonal. One way to optimize this further would be to scan the file one line at a time instead of load it all into a 2D array, then calculate both diagonals at the same time on one pass.

So in sudo code:

for each row i=0
    sumLeftToRight += line[i];        
    sumRightToLeft += line[size-i-1];   

print sumRightToLeft - sumLeftToRight

JS Fiddle

Answer 2

Aside from optimising the code, you should perhaps also do some error checking and validation:

• you have an input line that provides length, but you are just discarding the value and not checking it
• check that the input array is actually square--i.e. length of each line of input == height
• when you've got an if test, consider handling the else case - an example is your if at line 5.

If you validate the input, then that will probably help with figuring out why some tests are failing.

Answer 3

function diagonalDifference(arr) {

let d1 = 0;
let d2 = 0;

let j = 0;
let k  = arr.length-1;


for(let i = 0; i < arr.length; i++){
    // from left to right
    d1 += arr[i][j]
    j++;

    // from right to left
    d2 += arr[i][k]
    k--;

}

const diff = Math.abs(d1-d2)
return diff;

}

Answer 4

Below code calculate matrix diagonal difference in O(N) time

public class DiagonalDiffererence {

    public static void main(String args[]) {

        int a[][] = new int[][] { { 11, 2, 4 }, { 4, 5, 6 }, { 10, 8, -12 }};
        int left = 0;
        int right = a.length - 1;
        int leftDig = 0;
        int rightDig = 0;
        for (int i = 0; i < a.length; i++) {
            leftDig += a[i][left++];
            rightDig += a[i][right--];
        }
        int sum = Math.abs(leftDig - rightDig);
        System.out.println(sum);
    }

Answer 5

Helps to visualize the matrix in 2D array form with indexes.

(0,0) (0,1) (0,2)

---

(1,0) (1,1) (1,2)

---

(2,0) (2,1) (2,2)

---

So sum of d1 = (0,0) + (1,1) + (2,2) => d1 += arr[i][i] and sum of d2 = (0,2) + (1,1) + (2,0) => d2 += arr[i][(arr.length-1) - i]

function diagonalDifference(arr) {
    let d1 = 0;
    let d2 = 0;
    
    for(let i = 0; i<arr.length ; i++) {
        d1 += arr[i][i]; 
        d2 += arr[i][arr.length - 1 - i]; 
    }
    
    return Math.abs(d1-d2)
}

Answer 6

I have written the following code:

public static void main(String[] args) {

    Scanner in = new Scanner(System.in);

    int n = in.nextInt();
    int a[][] = new int[n][n];

    for(int a_i=0; a_i < n; a_i++){
        for(int a_j=0; a_j < n; a_j++){
            a[a_i][a_j] = in.nextInt();
        }
    }

    int count=0;
    int sum1=0;
    int sum2=0;

    for(int i=0,j=n;i<n && j>0;j--,i++){
        if(count==i){
            sum1=sum1+a[i][count];
            sum2=sum2+a[j-1][count];
            count++;
        }
    }

    System.out.println(Math.abs(sum1-sum2));
}