Rotate image#

Levels: level-3

Data structures: array

Practice Link#

LeetCode

Description#

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).

Note:

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#

 1Given input matrix =
 2[
 3  [1,2,3],
 4  [4,5,6],
 5  [7,8,9]
 6],
 7
 8rotate the input matrix in-place such that it becomes:
 9[
10  [7,4,1],
11  [8,5,2],
12  [9,6,3]
13]

 1Given input matrix =
 2[
 3  [ 5, 1, 9,11],
 4  [ 2, 4, 8,10],
 5  [13, 3, 6, 7],
 6  [15,14,12,16]
 7],
 8
 9rotate the input matrix in-place such that it becomes:
10[
11  [15,13, 2, 5],
12  [14, 3, 4, 1],
13  [12, 6, 8, 9],
14  [16, 7,10,11]
15]

Python Solution#

 1class Solution(object):
 2    # Pythonic with extended slices and zip syntax
 3    def rotate(self, A):
 4        """
 5        :type matrix: List[List[int]]
 6        :rtype: None Do not return anything, modify matrix in-place instead.
 7        """
 8        A[:] = list(zip(*A[::-1]))
 9
10    # first transpose and then flip left-right
11    def rotateManual(self, A):
12        n = len(A)
13        for i in range(n):
14            for j in range(i):
15                A[i][j], A[j][i] = A[j][i], A[i][j]
16        for row in A:
17            for j in range(n / 2):
18                row[j], row[~j] = row[~j], row[j]