Problem statement

https://leetcode.com/problems/rotate-image/

Solution

The idea behind if all elements can be divided into groups of 4 and swapped in loops. There are 2 slightly different cases we need to handle: case of odd n, for example: 1,2,3 -> 7,4,1

4,5,6 -> 8,5,2

7,8,9 -> 9,6,3

In this case we need to change groups 1 -> 7 -> 9 - > 3 -> 1, 2 -> 4 -> 8 -> 6 -> 2 and 5 -> 5.

In the case of even n, for example:

05,01,09,11 -> 15,13,02,05

02,04,08,10 -> 14,03,04,01

13,03,06,07 -> 12,06,08,09

15,14,12,16 -> 16,07,10,11

We need to change 4 groups of numbers 05 -> 15 -> 16 -> 11 -> 05, 01 -> 13 -> 12 -> 10 -> 01, 02 -> 14 -> 07 -> 09 -> 02, 04 -> 03 -> 06 -> 08 -> 04.

Actually, these two cases can be written in one condition if we carefully choose ranges in which we iterate.

Complexity

Time complexity will be O(n^2), space complexity is O(1), because we do not use any additional space.

class Solution:
    def rotate(self, M):
        n = len(M) - 1
        for i in range((n+2)//2):
            for j in range((n+1)//2):
                M[i][j], M[j][n-i], M[n-i][n-j], M[n-j][i] = M[n-j][i], M[i][j], M[j][n-i], M[n-i][n-j]