'Time Complexity of HackerRank Diagonal Difference

Can anyone help me identify the time complexity of the following code?

Background: this is a HackerRank algorithm problem where the editorial section lists the solution with a time complexity of O(n^2) but I think its O(n).

I believe its O(n) because we're only using one loop to traverse the 2 dimensional array and are not using nested loops and only looping over the array once.

Am I correct or am I missing something?

Solution

//arr is a 2 dimensional array containing an equal number of rows and columns
function diagonalDifference(arr) {
  let diff = 0;
  const length = arr.length - 1;
  for (let i = 0; i < arr.length; i++) {
    diff += arr[i][i] - arr[i][length - i];
  }
  return Math.abs(diff);
}

Problem

Given a square matrix (AKA 2D Array), calculate the absolute difference between the sums of its diagonals.

For example, the square matrix arr is shown below:

1 2 3 4 5 6 9 8 9

The left-to-right diagonal = 1 + 5 + 9 = 15. The right to left diagonal = 3 + 5 + 9 = 17. Their absolute difference is |15 - 17| = 2.

javascriptarraysalgorithmmultidimensional-array


Solution 1:[1]

Am I correct or am I missing something?

You are right, but I think their categorization of O(n^2) may be due to the interpretation wherein n refers to the n of the input (i.e. the side-length of the matrix). In this case, the number of elements in the matrix itself is exactly n^2, and thus any solution (since any solution must read in all n^2 inputs) is ?(n^2) (where ? roughly means "at least").

Your categorization of the solution as O(n) is correct if we say that n refers to the size of the whole input matrix.

Solution 2:[2]

The time complexity of the code is O(n) where is the length of the matrix. As you have correctly said the loop is running only once and that too equals the number of rows/ columns viz the length of the matrix. there are no nested loops. So the time complexity is definitely, O(n) for all the cases best, worst, avg.

Solution 3:[3]

My solution:

function diagonalDifference(arr) {
let leftDiagSum = 0;
let rightDiagSum = 0;
for (let i = 0; i < arr.length; i++) {
    leftDiagSum += arr[i][i];
    rightDiagSum += arr[i][arr[i].length - (i + 1)];
}
let sum = Math.abs(leftDiagSum - rightDiagSum);
return sum;

}

Solution 4:[4]

You can try this also:

`

function diagonalDifference(arr) {
    let firstDiagonalSum = arr[0][0] + arr[1][1] + arr[2][2];
    let secondDiagonalSum = arr[0][2] + arr[1][1] + arr[2][0];
    let result = (secondDiagonalSum) - (firstDiagonalSum);
    
    return result;
}`

Solution 5:[5]

in python :

def diagonalDifference(arr):
    
    d1 = 0
    d2 = 0
    n = len(arr)

    for i in range(0, n):
        for j in range(0, n):
            
            if (i == j):
                d1 += arr[i][j]
    
            if (i == n - j - 1):
                d2 += arr[i][j]
        
    return abs(d1 - d2)

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Kevin Wang
Solution 2 Ashish
Solution 3 Ivan Daniliuk
Solution 4 Ibe Kingsley Chibueze
Solution 5 wildan maulana

Related Questions