Absolute difference between diagonals of matrix

An algorithm to find the absolute difference between diagonals of a given matrix.

We will implement a simple algorithm to find the absolute difference between the diagonals of the matrix in javascript. Everything will be written in ES6.

Example

Input:
1, 2, 2
4, 25, 6
7, 8, 9

Output:
(1 + 25 + 9) - (7 + 25 + 2) = 1

Implementation

  • We will use two trackers top, bottom to calculate the sum of both the diagonals in single loop.
  • We will loop through the length of the column of the matrix and sum the elements of the diagonals.
  • In each iteration will we will increase the top++ and decrease the bottom-- so that we are moving diagonally in the matrix.
let matrixDiff = (arr) => {
  //Store the sum of the diagonals
  let d1 = 0;
  let d2 = 0;

  //Keep track of the diagonals
  let top = 0;
  let bottom = arr.length - 1;

  //Loop through the length of column 
  //and sum all the elements of the diagonals
  for(let i = 0; i < arr[0].length; i++){
    d1 += arr[top++][i];
    d2 += arr[bottom--][i];
  }
  
  //Return the absolute difference
  return Math.abs(d1 - d2);
}
Input:
let arr = [
  [1, 2, 2],
  [4, 25, 6],
  [7, 8, 9]
]

console.log(matrixDiff(arr));

Output:
1

How it works

  • We begin the loop at top = 0 and bottom = arr.length - 1.
  • At first iteration the first element of the first row is added to d1 and last element of first row is added to d2.
  • As we are doing top++ it will first execute the code and then increment the count, so top = 1 after first iteration, same for the bottom--.
  • Now in second iteration the second element of the second row is added to d1 and second last element of second row is added to d2.
  • This will continue for all the columns of the matrix.
1, 2, 2
4, 25, 6
7, 8, 9

d1 = 1;
d2 = 7;

/***************/

1, 2, 2
4, 25, 6
7, 8, 9

d1 = 26
d2 = 32

/**************/

1, 2, 2
4, 25, 6
7, 8, 9

d1 = 35
d2 = 34

Time complexity: O(m) where m is the length of the column.
Space complexity: O(1).

Time and Space complexity

  • We are iterating over all the columns of the matrix, so Time complexity is O(m) where m is the length of the column.
  • We are using constant space, so Space complexity is O(1).

Comments

  • My brother suggested I might lіke tһis website. He was totalⅼy right.
    This post trulу made my day. You cann’t imagine simply how much time І had spent for
    thіs infо! Thanks!

Leave a Reply

Your email address will not be published. Required fields are marked *