Matrix in JavaScript at The Hacking School Bootcamp — Sum elements of diagonals of a Matrix in O(n)

Image for post
Image for post

Problem Statement — Given a square matrix of numbers ( i.e. an array of arrays, in other words, a 2D matrix of numbers), write a function to get the sum of the 2 diagonals.

So for an example,

let matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9] ]

That is, in a 2-D form, the matrix is — [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ];

And the diagonal sum function should output 15, 15

I came up with the below solution, that works in O(n) time because, although the array is a 2-D one, I am traversing the array only once to access the relevant diagonal’s element numbers, i.e. a single loop for calculating sum of both the diagonals:

Now lets understand the mechanism and flow of the function.

For diagonal-1

A> For above example matrix, the elements across diagonal1 is [1, 5, 9] . So I am accessing the first element (i.e. 1) of diagonal1 > which is matrix[row0][row0] > which is matrix[1st element of outer array][first element of inner array] — in JS code which is matrix[0][0].

Note that because its a square matrix, the outerArray.length == innerArray.length

Hence to access the first element position of the inner array, and the innerArray being the first element of the outer array, I just do matrix[0][0]

B> The second element (i.e. 5) > which is matrix[2nd element of outer array][2nd element of inner array] > in JS code this is matrix[1][1]

So in similar way, starting from row index = 0, each element of the diagonal1 would be matrix[row][row].

So the general rule, for getting the elements of diagonal, I am incrementing both the positional values of the outer and inner array by one with each loop.

Now for diagonal-2

A> The diagonal2 is [3, 5, 7]. So I am accessing the first element (i.e. 3) >

which is matrix[First element of outer array][Last element of inner array] > In code which is matrix[0][2]

B> Then the second element of diagonal2 (i.e. 5) would be >

matrix[Second element of outer array][Last but one element of inner array]

which is is matrix[1][1]

C> Then the second element of diagonal2 (i.e. 7) would be >

matrix[Third element of outer array][First element of inner array]

which is is matrix[2][0]

So the general rule, for getting the elements of diagonal, with each loop, I am incrementing the positional index values of the outer array starting from index=0; BUT for the inner array I am decrementing the positional-index values starting from innerArray.length-1 .

So for the diagonal2, for the innerArray, the problem is of finding the element position from the last element towards left, i.e. looping the innerArray from reverse position.

So overall my for loop iterations will give me the below index values for diagonal-2:

  1. matrix.length = 3, i = 0 => we get the element (0, 3 — 0 — 1) = (0, 2)

Explanation of the part — matrix[row][matrix.length-row-1]

Generally whenever, I have reverse-loop an array (like in the more general problems of reversing an array), starting from its last element, I do this

array.[array.length - index - 1]

Here, the argument “index” is the index of the current element being processed, ie. it will start form index=0 of the given original array.

So for the first iteration (index = 0 i.e. in this specific problem row = 0), it will give me > array.[array.length-1–0] > which is the last element of the array.

A> Then for the second loop, index-value (i.e. row value in this specific problem) will be 1, i.e. I am accessing the element (array.length — 1–1). That is the element at array.length — 2 position, i.e. the second-last position.

B> And this way, for the last loop, I will be accessing array[(array.length-(length-1)-1] element, i.e. the array[0] position’s element of the original array.

So, the following pseudo code for this problem would make more sense now.

  1. Condition for Diagonal-1: The row-column condition is row = column.

And now just take a look at a sub-optimal solution in O(n²) traversing 2 loops

Written by

DataScience | ML | 2x Kaggle Expert. Ex Fullstack Engineer and Ex International Financial Analyst.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store