Leetcode 48. Rotate Image (Difficulty: medium)

Statement:

Link

You're given an nxn 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]]

My Solution:

n = len(matrix)
if n%2 == 0:
    rings = (n//2) + (n%2)
else:
    rings = (n//2) + (n%2) - 1

for j in range(rings):
    if n-2*j > 1:
        for i in range(j,n-j-1):
    	    carry1 = matrix[i][(n-1)-j]
            carry2 = matrix[(n-1)-j][(n-1)-i]

	    matrix[i][(n-1)-j] = matrix[j][i]
            matrix[(n-1)-j][(n-1)-i] = carry1

	    matrix[j][i] = matrix[(n-1)-i][j]
            matrix[(n-1)-i][j] = carry2

Explanation:

While thinking about this problem, I realized that a clockwise rotation by 90 degrees of any square matrix is the continuous exchange of four distinct elements on each step as shown in the image above. That is, if we were to see a matrix as a collection of concentric rings with inner rings diminishing by two dimensions on each step, then their rotation would consist of taking first their four corners and rotating them. Followed by the next four elements close to them, and so on. See image below for a visual understanding. After finishing rotating a certain ring, the next step is the following inner ring until reaching two different scenarios: a 2x2 matrix or a 1x1 matrix depending on whether the initial dimension was even or odd, respectively.

The code's first part determines the number of rings depending if the dimension n is even or odd. As each inner ring decreases its dimension by two compared to the previous one, the most minor cases are: 2x2 or 1x1. The if statement tells not to do anything for the latter scenario. For last, the second for-loop is designed to move the collection of distinct sets with four-elements on each ring. 

I used matrix notation (Aij) and inductive reasoning to derive the formulas.

The time complexity of this solution is O( n x(n/2) ) whereas the memory one is O(1).