LC 48 Rotate image

General idea

Rotate image is essentially rotating each outer layer by 90 degrees until we reached the inner-most layer.(for odd size matrix, that’s the single number in the middle, for even size matrix, that is the matrix with length 2 in the middle).

How many layers needed to rotate

For a matrix with length n, there will be n // 2 layers.

Rotate

Example

a b c    g d a 
d e f -> h e b 
g h i    i f c  

Rotating groups

In each layer, we have 4 groups that need to swap. Each group will have size (layer_len – 1). So for our example above, the outerlayer has size 3 so the group size is 2. They are [a,b], [c,f], [i,h], [g,d].

And each group swap with the next group in a clock-wise fashion.

We also notice that, the first group will always starts on matrix[j][j] and moves in horizontal fashion.
The second group will always start on matrix[j][j + group_size] and moves horizontally.

class Solution:
    def rotate(self, matrix: 'List[List[int]]') -> 'None':
        """
        Do not return anything, modify matrix in-place instead.
        Basically, we want to transpose the matrix. 
        A_{ij} = A_{ji}}
        """
        size_group = len(matrix) - 1
        for i in range(len(matrix)//2):
            pos = 0
            for j in range(size_group):

                temp = [matrix[i][i + pos],
                        matrix[i + pos][i + size_group],
                        matrix[i + size_group][i + size_group - pos],
                        matrix[i + size_group - pos][i]
                       ]
                matrix[i][i + pos] = temp[3]
                matrix[i + pos][i + size_group] = temp[0]
                matrix[i + size_group][i + size_group - pos]= temp[1]
                matrix[i + size_group - pos][i] = temp[2]
                pos += 1

            size_group -= 2


Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax