Matrix Looping: Now with a single loop

I’ve worked with matrix problems before and had always been curious how to cut down on their run time. The ways I’ve usually gone about solving a matrix problem was to write a nested loop in order to extract the values. However, that method leaves you with a On^2 runtime, which isn’t the most efficient.

The problem

Today, I came across a problem that asked me to approach matrix problems different.

Basically, I was tasked to find the sums of the diagonals of the matrix. Given a range of numbers from 1 to 9, the sum from the top left is 1 + 5 + 9 = 15 and from the top right is 3 + 5 + 7 = 15.

My first instinct to traverse the array was a nested for loop that would give me access to all of the values.

let (i = 0; i < matrix.length; i++{
    let (j = 0; j < matrix[i].length; j++){
    //add up the totals
    }
}

However, I quickly realized that wasn’t necessary. After, I don’t need all of the values, I only need the diagonals.

Visualizing the pattern

At this point, it was helpful for me to write down the values as the program would view them: as indexes in an array.

For the top left values, we can access them with matrix[0][0], matrix[1][1], matrix[2][2].

For the top right values, we can access them via matrix[0][2], matrix[1][1], matrix[2][0].

This step proved to be so helpful to understanding the problem. If you look at the pattern for the left values, we can see the values increment by 1 each time. For the top left, the first part increment by 1, and the latter half decrement by 1.

Since all of these values are incrementing (or decrementing) by the same value, we can use just one for loop.

One for loop

Tackling the left side of the problem is easy given what we already know from the pattern above. We just need to start at 0,0 and add 1 each time. This can be done with a for loop as we traverse each row of the matrix.

for (let i = 0; i < matrix.length; i++){
    left += matrix[i][i]
}

The first half of the right side is the same. We can use i to increment each row of the matrix.

For the second part, we’ll need the length of the matrix and/or row (assuming this matrix has the same number of rows as it does columns).

Why do we need the length of the row? We need to start at the end of the row, which is the length of the row.

With this in mind, let’s look at the pattern again: [0][2], [1][1], [2][0].

Since the length of our rows is 3, we’ll need to subtract 1 in order to start at 2. Then we can minus i each time. Since i starts at 0 on the first iteration, we’ll end up with 2.

Here’s the full problem. I’ve changed the variables slightly to make the code DRYer.

  let row = arr.length
  let left = 0, let right = 0

  for(let i = 0; i < row; i++){
    left += arr[i][i]
    right += arr[i][row - 1 - i]
  }

Summary

Instead of using a nested for-loop to pull out the values, we can use a single for loop to pull only the values we need. This cuts down the runtime to O^n.

Probably the most helpful method to approaching a problem like this is writing down the values as the program would see them. That way, you’ll be able to see the pattern (and realize that one loop would do just fine).

You can find this problem on hackerrank.