Rotate Image
It's been a really busy week! On Tuesday evening I played my first show in probably two years (since before the pandemic started). I joined my friend Lindsey's band, Little Mazarn, and we did cello arrangements of her songs. It was wonderful to play music and create something beautiful in a collaborative way. Aside from that, work has been busy this week, with WordPress maintenance and an ACL taping. Anyway, today I have another Array problem from LeetCode to write about, this one is called Rotate Image.
Prompt
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1
Input:
matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9]]Output:
[ [7, 4, 1], [8, 5, 2], [9, 6, 3]]Example 2
Input:
matrix = [ [5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]Output:
[ [15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]Example 3
Input:
matrix = [ [1]]Output:
[ [1]]Example 4
Input:
matrix = [ [1, 2], [3, 4]]Output:
[ [3, 1], [4, 2]]Stating the Problem in My Own Words
I'll be given a 2D array of sub-arrays, named matrix, representing an image. If there are 2 sub-arrays, then each sub-array will have 2 elements. If there are 3 sub-arrays, then each sub-array will have 3 elements. My task is to write a function that rotates matrix 90 degrees, so that the first elements in each sub-array all become the elements in the first sub-array, the elements that were previously in the first sub-array all become the last elements in each sub-array, and so on. This is best represented visually:
[ [1, 2, 3], [4, 5, 6], [7, 8, 9]]The above image will be returned as:
[ [7, 4, 1], [8, 5, 2], [9, 6, 3]]The rotation will happen in place, so I won't be creating and returning a new array.
Approach: Two Loops, .pop(), and .unshift()
Similar to the Valid Sudoku problem, I think it's easiest to think about matrix as a set of coordinates:
00 | 01 | 02------------10 | 11 | 12------------20 | 21 | 22If we're looking at an item, let's say 00, we can think of the first digit as the row, and the second digit as the column, so 00 is row 0, column 0, or 21 is row 2, column 1.
The first place we're going to start is with a for Loop that iterates up through each row of the matrix.
function rotateImage(matrix) { for (let i = 0; i < matrix.length; i += 1) { // this will get us access to each sub-array in ascending order }}Okay, so that's the easy part. We're just looping to access each sub-array, but what do we do while we're there? Well let's break it down. Say we have the following matrix:
[ [1, 2, 3], [4, 5, 6], [7, 8, 9]]For the first iteration of our loop, we're looking at the first sub-array, [1, 2, 3]. We're going to now loop backwards within this sub-array, and start placing each item onto the row where it will ultimately end up. The last item of this sub-array will need to wind up in the last sub-array, so what we are going to do is use the .pop() method to remove it from the end of row 0 and then use .unshift() to attach it to the beginning of row 2. That would give us something like this:
[ [1, 2], [4, 5, 6], [3, 7, 8, 9]]Now we need to handle 2. We're going to once again .pop() it off of row 0, but this time we're going to .unshift() it onto row 1.
[ [1], [2, 4, 5, 6], [3, 7, 8, 9]]So now we're left with 1 in the first row. If you look at the solution above, 1 will be the last element on the rotated image. Even though it's where it needs to be, our loop will still need to .pop() it and then .unshift() it onto row 0.
[ [1], [2, 4, 5, 6], [3, 7, 8, 9]]Now that we've finished our first sub-array, it's time to move onto the second sub-array, and we're going to do the same three operations -- .pop() from the end, .unshift() onto rows in reverse index order: 2, 1, 0.
Our first iteration on this row gives us the following:
[ [1], [2, 4, 5], [6, 3, 7, 8, 9]]Then the second iteration:
[ [1], [5, 2, 4], [6, 3, 7, 8, 9]]Then the third iteration:
[ [4, 1], [5, 2], [6, 3, 7, 8, 9]]I hope the pattern here is starting to become clear. We're looping up through each sub-array. Within each sub-array, we're looping backwards, taking the items from the end of the sub-array, and placing them where they need to go. The last item needs to go into the last sub-array, the second-to-last item needs to go into the second-to-last sub-array, and so on.
We do this second iteration only as many times as there are sub-arrays within the matrix array. We can use a nested loop and a tracker variable to help us with this operation. Here's what that code looks like:
function rotateImage(matrix) { for (let i = 0; i < matrix.length; i += 1) { let tracker = matrix.length - 1; // number of times the inner loop needs to run for (let j = tracker; j >= 0; j -= 1) { const current = matrix[i].pop(); // remove the item at the end of the sub-array we're looping through, save it to a variable called current matrix[tracker].unshift(current); // attach current onto the front of the sub-array the loop is looking at tracker -= 1; // decrement tracker variable to look at prior sub-array } } return matrix; // really that's all, once outer loop has run we can simply return the image}That's about it, but let's pick up with where we left off and see how this pattern plays out. So when we finished the second outer loop iteration this is where we were:
[ [4, 1], [5, 2], [6, 3, 7, 8, 9]]So now we're looping 3 times through the third sub-array, and each time .unshift()ing the item onto a sub-array, starting from the last sub-array. For the next iteration we're looking at 9:
[ [4, 1], [5, 2], [9, 6, 3, 7, 8]]Now 8:
[ [4, 1], [8, 5, 2], [9, 6, 3, 7]]Finally 7:
[ [7, 4, 1], [8, 5, 2], [9, 6, 3]]And at this point our loops have finished, our matrix is rotated, and we just need to return it.
So to drive the point home, think about this matrix grid. If there are x sub-arrays of x length, then there will be x * x .pop() and .unshift() operations.
00 | 01 | 02 // 0.pop() -> 2.unshift(), 0.pop() -> 1.unshift(), 0.pop() -> 0.unshift()------------10 | 11 | 12 // 1.pop() -> 2.unshift(), 1.pop() -> 1.unshift(), 1.pop() -> 0.unshift()------------20 | 21 | 22 // 2.pop() -> 2.unshift(), 2.pop() -> 1.unshift(), 2.pop() -> 0.unshift()Solution
function rotateImage(matrix) { for (let i = 0; i < matrix.length; i += 1) { let tracker = matrix.length - 1; for (let j = tracker; j >= 0; j -= 1) { const current = matrix[i].pop(); matrix[tracker].unshift(current); tracker -= 1; } } return matrix;}Big O of this Solution
The Big O of this solution for Time Complexity is O(n²) since we have two loops, one nested in the other. If we have 3 sub-arrays of 3 items, then that's 9 .pop() and .unshift() operations. If we have 4 sub-arrays of 4 items, then that's 16 operations. It's also worth noting that .unshift() is an expensive operation when working with arrays, since adding an item to the beginning of an array requires re-indexing all of the subsequent items.