JavaScript Problem Solvers: Rotate Image Matrix

CASE 010: In Line And In Time

It’s been a while since I’ve written a blog about a technical problem I’ve solved. The truth is I haven’t been grinding on HackerRank or LeetCode as much as I used to, and all of my time has been spent working on projects.

That changed this week. Today’s problem took me a long time to solve, longer than I’d like to admit, but provided a great opportunity to shake out the cobwebs and get back on that LeetCode grind. The solution I came up with meets the O(1) space complexity requirement, and runs in O(n * log n) time complexity (I think).

I’d also like to mention that I found CodeSignal recently, and I have been enjoying it so far. I only just started their Interview Practice track, but the UI is a step up from LeetCode/HackerRank, their feature sets and test cases are solid, and the amount of information given for each problem has been good. Check it out if you need a change of scenery.

So, let’s get solving.

THE PROBLEM

Here is a link to the problem on Code Signal

You are given an n x n 2D matrix that represents an image. Rotate the image by 90 degrees (clockwise).
Note: Try to solve this task in-place (with O(1) additional memory), since this is what you’ll be asked to do during an interview.
Constraints:
  1 ≤ a.length ≤ 100
  a[i].length = a.length
  1 ≤ a[i][j] ≤ 104
Input/Output:
  [execution time limit] 4 seconds (js)
  [input] array.array.integer a
  [output] array.array.integer

THE TESTS

THE BREAK DOWN

On the surface, this seems simple. But there is a spanner in the works. So, as we always do, let’s break down the information given to us before doing anything else:

You are given an n x n 2D matrix that represents an image.

We get a very important piece of information in the first sentence: n x n 2D matrix. n x n represents the number of rows/columns we should expect in a given matrix, and since the matrix is n x n, the number of rows will always be equal to the number of columns. This is huge, as it means the matrix is linearly dependent, and if we want to, we can perform operations on both rows and columns within the same iteration.

Rotate the image by 90 degrees (clockwise)

This is our task. In the context of a n x n 2D matrix, we basically need to flip each row into a column. But we need to do so inversely.

So, if we look at Test Case #2:

This took me a while to visualize, or at least visualize in relative to how to do it with code, so I wanted to go over it here.

Note: Try to solve this task in-place (with O(1) additional memory), since this is what you’ll be asked to do during an interview.

This is the twist that makes things interesting.

I interpreted this to mean:

This is a sorting algorithm: Swap numbers and set variables only
No extra data sets: No objects to store indices. No empty arrays to push into. Nothing. Everything must be done inline.
No built in array methods: Since I am not 100% sure on the space complexity for each individual method in JavaScript (maybe I should be), that means no built in methods. No reverse(), map(), sort(), filter(), indexOf(), shift(), push(), etc.

Are there methods with O(1) space complexity? Of course.

Did I want to use them? No.

THE CONSTRAINTS

I am not going to worry about the majority of the usual edge cases we might encounter. All of the potential edge cases I could think about were covered by the constraints:

1 ≤ a.length ≤ 100

a represents the entire matrix, and a.length represents the amount of rows and columns. Since we have a lower limit of 1 ≤ a.length, we do not have to worry about a given matrix being empty. No if statements handling edge cases are needed. The upper limit of a.length ≤ 100 tells me we are going to have to be careful about the time complexity of our solution. 100 rows and 100 columns is a lot to cycle through.

a[i].length = a.length

This is a reaffirmation of what we were told before: n x n 2D matrix. a[i].length = a.length is just another way of saying “The amount of rows in a given matrix will always be equal to the amount of columns.”

1 ≤ a[i][j] ≤ 104

a[i][j] represents each number in the matrix. While this is not the most essential constraint we get (all we are doing is swapping numbers around), it is always good to have lower and upper limits on the elements we should expect.

With that being said, let’s move onto solving this problem.

THE SUSPECT

I wrote more pseudo code for this problem than any other problem I’ve ever solved, and spent way more time writing pseudo code than writing/testing actual code. So I am going to structure this blog a little differently.

First, I want to go into more detail about each iteration. My solution follows an onion-like swapping pattern, or what I am going to call Onion Swap.

To demonstrate, let’s take Text Case #3:

Starting at row[0][0], we want all of the numbers to move in a clockwise pattern. At the end of the first iteration, we want row[0][0] to be the correct number regardless of what we do. So, for Test Case #3, we want 6 to be 5, which is located at row[3][0]. We don’t want to have to go back to row[0][0] throughout the rest of the execution of our code, so it has to end up as the correct number in order for this to work. We are visiting it once each iteration and that’s it.

The same goes for each corner. At the end of the first iteration, each corner must be at it’s correct and final value.

We can do this on the first iteration by nesting a second iteration, and swapping the values of each corner:

After performing these 3 swaps, each value at the corners of the matrix are in their correct and final positions, and we never have to worry about them again.

On the 2nd loop of our iteration, we can repeat the same process for the number at row[0][1], and swap it with the next number in the layer:

We now have another set of numbers in the correct position. We can repeat this swapping pattern 1 more time on the 3rd iteration of our nested loop and get all of the numbers in the outer most layer of the matrix in their correct and final positions:

We also want our nested loop to only run 3 times since we have already swapped the last element in row[0] with row[0][0]. We can do this by setting the upper limit of our nested loop to a.length - 1.

This Onion Swap will also work on any inner layer in the matrix as well. The same pattern of flipping the numbers clockwise remains true. We can increment and use i and j to access each subsequent layer.

If we set j = i, on the 2nd iteration of the entire loop where i = 1, we can access the inner layer of Test Case #3:

All the values in the “inner layer” of the matrix are now in their correct and final position as well. The entire matrix has been rotated 90 degrees clockwise and it only took 4 iterations. We can exit out of our loop and return a.

THE VARIABLES

Now that we've found a repeatable pattern to follow that rotates the matrix 90 degrees, we need to start setting up and assigning variables so we can get this pattern to work with any n x n matrix given to us.

If we take a look at the operations for each iteration, there is a pattern:

So that tells me we are going to need extra variables to increment and decrement through each loop of the nested iteration. We can use j for the variable we need to increment as j naturally increments through each nested iteration.

But we will need to add another variable we can decrement…somewhere.

If we set j = i, we can replace row[0][0] with row[i][j] as j will naturally start in the correct position on every re-iteration for each inner layer. With Onion Swap, j starts outwards and works inward.

But a problem arises when we look at the 2nd loop of the entire iteration:

The first part looks fine. But the pattern for the 2nd part isn’t the same as the first iteration. The “inner layer” of Test Case #3 is 2 x 2, and represents the smallest sub-matrix we would need to swap numbers for.

That’s okay. The pattern still remains true for every layer of the matrix that isn’t 2 x 2. We can solve this by initializing the variable we are decrementing in the parent for loop with (a.length - 1) - i and scope it outside the nested iteration to prevent it from resetting every time the nested loop iterates.

Let’s take another look at our iterations, but add in the variable we want to decrement x, and substitute the appropriate static values with x, i and j:

That leaves us with 1 static value we need to figure out.

And from the looks of it, it follows a pattern as well. It remains constant within each nested loop, but needs to be decrements by 1 on each iteration of the entire loop. So, we can use that and add another variable y that is initialized with a.length - 1. This is to make sure it remains dynamic to the size of a given matrix. We can also scope it outside both loops so it does not reset throughout the entire execution of our solution, and decrement y every time the entire for loop iterates:

That fulfills all of the variable requirements needed to put this Onion Swap stuff into practice.

THE SETUP

So, let’s actually put this into code.

The way the two for loops are going to work is like this:

The parent loop will iterate through each “layer” of the matrix. The amount of “layers” a matrix has is determined by half it’s length or a.length / 2. So if we set the parent loop’s upper limit to i < a.length / 2 it should properly iterate through every “layer” of the matrix, without wasting any iterations. If it does, this entire house of cards will come crashing down.

The nested loop is what is looping through the elements in each row and column. The amount of elements in each row/column will always be equal, but for every inner “layer,” the amount of rows/columns/elements we need to iterate through gets smaller and smaller, until we reach the center.

For a given matrix, if n x n is an even number, then the center of the matrix will be 2 x 2, and we will need to perform 1 last Onion Swap. If n x n is an odd number, the center of the matrix will be 1 x 1, for which we don’t need to swap anything, and we can exit out of our iterations.

That makes sense if we look back at the pattern we needed the y variable for. It’s basically an upper bound for the position of elements we want to iterate through on each inner layer. So we can use y as an upper bound in our nested loop and set j < y to prevent looping through layers that don’t exist.

With that being said, we can set up our two for loops, our variables, and how we want to decrement the x and y variables:

And in the middle of that for loop sandwich, we can add all of the Onion Swap logic. We just need to remove the pseudo code and replace row with a:

THE FINAL SOLUTION

The only problem (and last problem) with the code we have written, is that we technically aren’t swapping anything. We are just replacing the value a[i][j] is currently at.

We need 1 more variable t to store the number we are currently swapping so we can swap it with the number we are replacing it with:

let t = a[i][j]

Then we need to swap that temporary variable with the value at the position we just swapped a[i][j] with:

a[j][y] = t or a[y][x] = t or a[x][i] = t

Then, we need to update t’s value with the new value of a[i][j] so we can repeat the process again for our 2nd and 3rd swaps of the iteration:

t = a[i][j]

Finally, if we run our solution against the 5 test cases we have, we should be passing every test:

Nice.

MISSION COMPLETE

So that was a mouth full, but a good problem to come back to after a month of not grinding. I also really like the solution I came up with (usually I’m not as satisfied), and making the Onion Swap work really pushed my problem solving abilities. At some point, I just really wanted to get it working, which is probably why I spent so much time on it.

Did I over complicate things? Maybe. But it was worth the effort, and surprisingly efficient.

Once again, the blogs I write about solving LeetCode/HackerRank/CodeSignal problems aren’t about finding the solution with the lowest time or space complexity. Their focus is on the steps taken to come to a solution. I definitely understand my solutions won’t be the best or most efficient, but this time around I am pretty happy with the outcome.

Either way, I hope you got some useful information, and may all your functions return true, and all your requests respond with 200.

Stay safe…stay healthy…and keep fighting the good fight.