Skip to content

Latest commit

 

History

History
106 lines (79 loc) · 1.69 KB

m0048.md

File metadata and controls

106 lines (79 loc) · 1.69 KB

Rotate Image

Question Stem

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:

[
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]

output:

[
    [7, 4, 1],
    [8, 5, 2],
    [9, 6, 3],
]

Example 2:

input:

[
    [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],
]

Idea

From the perspective of linear algebra, the function can be viewed as a linear transformation Ax + b.

The input x:

x 0 1 2 3
y
0 5 1 9 11
1 2 4 8 10
2 13 3 6 7
3 15 14 12 16

can be first rotated pi/2 (A * x):

x -3 -2 -1 0
y
0 15 13 2 5
1 14 3 4 1
2 12 6 8 9
3 16 7 10 11

Example:

  1. point 1: [1, 0]:

    [0, -1] [1] = [0]
[1,  0] [0] = [1]

  2. point 8: [2, 1]:

    [0, -1] [2] = [-1]
[1,  0] [1] = [ 2]

add interception [3, 0]:

x 0 1 2 3
y
0 15 13 2 5
1 14 3 4 1
2 12 6 8 9
3 16 7 10 11

Source Code

  1. python