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 thebottom--
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
andbottom = 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 tod2
. - As we are doing
top++
it will first execute the code and then increment the count, sotop = 1
after first iteration, same for thebottom--
. - Now in second iteration the second element of the second row is added to
d1
and second last element of second row is added tod2
. - 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).
caputo says:
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!