Solution: Rotate Image

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #48 (Medium): Rotate Image

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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.

---

Examples:

Example 1:
Input:	matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output:	[[7,4,1],[8,5,2],[9,6,3]]
Visual:

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]]
Visual:

Example 3:
Input:	matrix = [[1]]
Output:	[[1]]

Example 4:
Input:	matrix = [[1,2],[3,4]]
Output:	[[3,1],[4,2]]

---

Constraints:

• matrix.length == n
• matrix[i].length == n
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

The trick here is to realize that cells in our matrix (M) can be swapped out in groups of four in a self-contained manner. This will allow us to keep our space complexity down to O(1).

The remaining difficulty lies in setting up our nested for loops to accomplish the entirety of these four-way swaps. If we consider each ring of data as a larger iteration, we can notice that each successive ring shortens in the length of its side by 2. This means that we will need to perform this process to a maximum depth of floor(n / 2) times. We can use floor here because the center cell of an odd-sided matrix will not need to be swapped.

For each ring, we'll need to perform a number of iterations equal to the length of the side minus 1, since we will have already swapped the far corner as our first iteration. As noticed earlier, the length of the side of a ring is shortened by 2 for each layer of depth we've achieved (len = n - 2 * i - 1).

Inside the nested for loops, we need to perform a four-way swap between the linked cells. In order to save on some processing, we can store the value of the opposite side of i (opp = n - 1 - i) as that value will be reused many times over.

Once the nested loops are finished, M has been successfully transformed in-place.

• Time Complexity: O(N^2) where N is the length of each side of the matrix
• Space Complexity: O(1)

---

Implementation:

There are only minor differences between the code of all four languages.

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var rotate = function(M) {
    let n = M.length, depth = ~~(n / 2)
    for (let i = 0; i < depth; i++) {
        let len = n - 2 * i - 1, opp = n - 1 - i
        for (let j = 0; j < len; j++) {
            let temp = M[i][i+j]
            M[i][i+j] = M[opp-j][i]
            M[opp-j][i] = M[opp][opp-j]
            M[opp][opp-j] = M[i+j][opp]
            M[i+j][opp] = temp
        }
    }
};

---

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def rotate(self, M: List[List[int]]) -> None:
        n = len(M)
        depth = n // 2
        for i in range(depth):
            rlen, opp = n - 2 * i - 1, n - 1 - i
            for j in range(rlen):
                temp = M[i][i+j]
                M[i][i+j] = M[opp-j][i]
                M[opp-j][i] = M[opp][opp-j]
                M[opp][opp-j] = M[i+j][opp]
                M[i+j][opp] = temp

---

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public void rotate(int[][] M) {
        int n = M.length, depth = n / 2;
        for (int i = 0; i < depth; i++) {
            int len = n - 2 * i - 1, opp = n - 1 - i;
            for (int j = 0; j < len; j++) {
                int temp = M[i][i+j];
                M[i][i+j] = M[opp-j][i];
                M[opp-j][i] = M[opp][opp-j];
                M[opp][opp-j] = M[i+j][opp];
                M[i+j][opp] = temp;
            }
        }
    }
}

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    void rotate(vector<vector<int>>& M) {
        int n = M.size(), depth = n / 2;
        for (int i = 0; i < depth; i++) {
            int len = n - 2 * i - 1, opp = n - 1 - i;
            for (int j = 0; j < len; j++) {
                int temp = M[i][i+j];
                M[i][i+j] = M[opp-j][i];
                M[opp-j][i] = M[opp][opp-j];
                M[opp][opp-j] = M[i+j][opp];
                M[i+j][opp] = temp;
            }
        }
    }
};

Comments

[Daniel Hao]

It can be solved using the zip + reversed(matrix) like

def rotate(matrix):
'''in-place rotate'''
matrix[:] = [list(r) for r in zip(*reversed(matrix))]