Rotate Image medium

Problem Statement

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: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2:

Input: matrix = [[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]]

Steps:

1. Transpose the matrix: A transpose swaps rows and columns. This is a crucial first step because it lays the groundwork for the final swapping.

2. Reverse each row: After transposing, each row represents a column in the rotated image. Reversing these rows completes the 90-degree clockwise rotation.

Explanation:

Let's break down why this works. Consider a simple 3x3 matrix:

[ a b c ]
[ d e f ]
[ g h i ]

Step 1: Transpose

Transposing swaps rows and columns:

[ a d g ]
[ b e h ]
[ c f i ]

Step 2: Reverse each row

Reversing each row gives us the 90-degree clockwise rotated matrix:

[ g d a ]
[ h e b ]
[ i f c ]

Code:

def rotate(matrix):
    """
    Rotates a square matrix 90 degrees clockwise in-place.

    Args:
      matrix: A list of lists representing the square matrix.
    """
    n = len(matrix)

    # Transpose the matrix
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

    # Reverse each row
    for i in range(n):
        matrix[i].reverse()


# Example usage:
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate(matrix)
print(matrix)  # Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

matrix = [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]
rotate(matrix)
print(matrix) # Output: [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]

Complexity:

• Time Complexity: O(n^2), where n is the dimension of the square matrix. We iterate through the matrix twice (once for transpose and once for reversal).
• Space Complexity: O(1). The rotation is done in-place; we don't use extra space proportional to the input size.