As I’m studying on HackerRank I came across the diagonal difference challenge. I’m definitely guilty of over-thinking and creating ways that resulted in wasted time.
After many tries, I eventually solved the challenge and I’m writing this article to simply explain it as a reference to myself and other developers. Let’s get started.
Given a square matrix, calculate the absolute value of the difference between the sums of its diagonals.
An example matrix is below:
The left-to-right diagonal is 1 + 5 + 9 = 15.
The right-to-left diagonal is 3 + 5 + 9 = 17.
The absolute difference is |15–17| = 2.
The given task is to create a function diagonalDifference. The only parameter it takes is an array of integers and the function needs to return the absolute difference.
To solve the challenge, we need to create 3 variables, representing the array’s length, the sum of the left-to-right diagonal, and the sum of the right-to-left diagonal, respectively.
As seen in the image above, 3 variables have been created. The left diagonal sum (lSum) and the right diagonal sum (rSum) are both set to 0, initially. The idea is to increment the value with the appropriate integers to get the correct sum value.
Next up, a for loop is required to set the locations for each diagonal sum. Since the diagonals are of opposite directions, we need to create an initial variable within the loop that will represent the left-most index integer. Then, a second variable is also created within the same loop to represent the right=most index integer.
As seen above, the for loop is initiated with a variable [i] set to 0, to represent the left-most index. A second variable [j] is also created and set to the last integer, which would be the array’s length minus 1.
The last bit of the for loop is something I didn’t realize I can do, but it’s how the left-most index will increment to go onto the following integer, and how the right-most index will decrement to the previous integer. All happening in one for loop.
The for loop results in the correct sums for both diagonals, now we can concentrate on returning the absolute difference.
And there we have it, a solution to the diagonal difference problem.
As a deeper analysis for the solution, the complexities are as follows:
Since we are iterating over all of the columns of the matrix, the time complexity would be O(n), where n is the length of the column.
This solution is using constant space and therefore the space complexity is O(1).