Solving Popular Algorithms: Matrix Diagonal Sums
Another week, another algorithm to solve…
This week we are going to be tackling another LeetCode problem. The problem is called Matrix Diagonal Sums and while it seems quite easy, it has a few tricky elements that I think are definitely worth going over. So, without further ado, let’s jump right into solving this problem!
The Problem
The goal of this problem is, given a square matrix, to sum numbers across both diagonals of the square.
If you are new to matrices, don’t worry. For the purposes of this problem, you can understand a matrix as basically an array of arrays. So, based on the image above, the matrix our function will receive would be:
mat = [[1,2,3],[4,5,6],[7,8,9]]Now you may be thinking that the answer to this example problem would be 30 as the numbers in our primary diagonal (1, 5, and 9) would sum together to equal 15 and the numbers in our secondary diagonal (3, 5, and 7) would also sum together to be 15. However, for this problem, we only want to sum numbers in our secondary diagonal that aren’t not included in our primary diagonal. As such, for our secondary diagonal we would not include 5, since that number was already summed in our primary diagonal. Thus, the correct answer to this example problem would be 25.
Remembering to exclude this overlapping number is an important and complicated part to this problem, however what’s helpful to note is that only odd length matrices will have an overlapping number.
Keeping all this mind, let’s jump right into our solution!
The Solution: Our Primary Sum
For my own problem solving purposes, I split the problem into three parts: finding the primary sum, finding the secondary sum, and getting rid of any potential overlapping numbers.
The first part, finding our primary sum, is definitely what I would considered to be the easiest portion of our problem. However, understanding the solution to this part of the problem will definitely help understand the rest of our solution!
So, the first thing I thought about when trying to solve this problem, was how I would get to each number in the diagonal. The first and last numbers were easy, as they would be the first number in the first row and the last number in the last row. The real trick to the problem is figuring out how to get the middle numbers.
What I quickly realized was that every number we needed for our primary diagonal was the subsequent number in the subsequent row for our previous number. For example, the first number we need in a 3x3 matrix, would be in row 0 at position 0 (remember arrays start with an index of 0!). The second number we would need would be in row 1 at position 1. And the final would be in row 2 at position 2.
With that realization, I came up with this code to help me to get the correct sum to the primary diagonal:
diagonalSum = (mat) => {
let primSum = 0
for (let i = 0; i < mat.length; i++) {
primSum += mat[i][i]
}
}Basically, we will loop through the our matrix and grab each element i in each row i and then increment. Then, we can add each of those elements to our primary sum and voila!
The Solution: Finding our Secondary Sum
Finding our secondary sum will be quite similar to finding our primary sum. In fact, we will only need to write one additional line of code.
To find our secondary sum, let’s think through how to find each number in our secondary diagonal, much like how we did with our primary diagonal. Like our primary diagonal, we will again start in row 0. This time, however, we will need the element at the end of the row, instead of at the beginning. Thus, in a 3x3 matrix, we will need the element in position 2 of row 0. To get our second number, we will add a row and move into row 1, but we will then subtract an element and grab the element in position 1. For our third number, we will again add a row and subtract an element, and thus, our final number will be in row 2 at position 0.
In code, that process will look something like this:
diagonalSum = (mat) => {
let primSum = 0
let secSum = 0 for (let i = 0; i < mat.length; i++) {
primSum += mat[i][i]
secSum += mat[i][mat.length-1-i]
}
}
Just to note, we subtract 1 from mat.length as arrays start with an index of 0.
Now that we have both our primary sum and our secondary sum, we can move onto the final part of our problem.
The Solution: Remove Overlapping Numbers
Like I talked about at the start of this guide, any matrix that is odd in length will have one overlapping number that can be found in both the primary and secondary diagonals. Since we want each number to only be added to our final sum once, we need to figure out a way to remove this overlapping number.
There are two important things to note about this overlapping number: first, as we’ve said before, we will only have an overlapping number in odd numbered matrices, and second, the overlapping number will be the number in the direct center of our matrix.
Keeping those things in mind, we can set up a simple if statement, checking to see if our matrix is odd as we don’t have to worry about this overlapping in even numbered matrices. Then, we can find the middle of the matrix using a handy JS method called floor. Math.floor() is a method that will round a number down to its nearest integer.
So in our 3x3 matrix, for example, we know that our middle number will be in row 1 at position 1. Using math.floor(), we can divide the length of matrix in half (3/2 = 1.5) which will then round down to give us the correct row and position in our matrix.
Thus, our completed solution will look like this:
diagonalSum = (mat) => {
let primSum = 0
let secSum = 0 for (let i = 0; i < mat.length; i++) {
primSum += mat[i][i]
secSum += mat[i][mat.length-1-i]
}
if (mat.length%2 !== 0) {
let mid = Math.floor(mat.length/2)
secSum -= mat[mid][mid]
}
return primSum + secSum}
I hope you found the guide helpful and definitely checkout this problem and give it a try yourself. My solution is definitely not optimized, so if you’re looking for a challenge, try to see if there’s a way to get a faster solution than mine! As always, good luck and happy coding!
