Diagonal Difference¶
This is a classic matrix problem. The “diagonal difference” is just the easy part (a subtraction). The main challenge here is to sum the diagonals of the given square matrix.
1 2 3
4 5 6
7 8 9
Basically, our goal is to sum 1, 5 and 9 from the right to left diagonal, 3, 5 and 7 from the left to right diagonal, and perform the subtraction.
JavaScript¶
Solution 1 with nested loops¶
/**
* Calculates the diagonal difference of the square matrix.
*
* T.C: O(n²).
* S.C: O(1).
*
* @sig [Number] -> Number
*/
function diagDiff(sqrMatrix) {
const len = sqrMatrix.length;
let ltrDiag = 0;
let rtlDiag = 0;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len; j++) {
if (i === j)
ltrDiag += sqrMatrix[i][j];
if (i + j === len - 1)
rtlDiag += sqrMatrix[i][j];
}
}
return Math.abs(ltrDiag - rtlDiag);
};
The time complexity is \(O(n^2)\) because of the nested looping.
Solution 2 with single loop¶
/**
* Calculates the diagonal difference of the square matrix.
*
* - T.C: O(n).
* - S.C: O(1).
*
* @sig [Number] -> Number
*/
function diagDiff(xs) {
let ltrDiag = 0;
let rtlDiag = 0;
let len = xs.length;
for (let i = 0; i < len; ++i) {
ltrDiag += xs[i][i];
rtlDiag += xs[i][len - i - 1];
}
return Math.abs(ltrDiag - rtlDiag);
}
With this implementation, the time complexity is \(O(n)\) (not \(O(n²)\) like in the previous solution) because the sum of the left and right diagonals are calculated within the same loop.
A combination of i
and len
is used so that indices are accessed from the left and right at the same time.
Because of len - i
, each time i
is incremented by the loop, that len - i
produces lower and lower indexes each time.
That len - 1 - 1
can be simplified a little bit:
/**
* Calculates the diagonal difference of the square matrix.
*
* - T.C: O(n).
* - S.C: O(1).
*
* @sig [Number] -> Number
*/
function diagDiff(xs) {
let ltrDiag = 0;
let rtlDiag = 0;
- let len = xs.length;
+ const lastPos = xs.length - 1;
for (let i = 0; i < len; ++i) {
ltrDiag += xs[i][i];
- rtlDiag += xs[i][len - i - 1];
+ rtlDiag += xs[i][lastPos - i];
}
return Math.abs(ltrDiag - rtlDiag);
}