Rotate Image

January 4, 2024

Problem: #

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 without using another 2D matrix.

Example: #

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Solution: #

Algorithm: Transpose and Reverse

The algorithm works in two steps. First, transpose the matrix (swap rows with columns), and then reverse each row.

Algorithm Steps: #

1. Transpose the Matrix: Swap the element at matrix[i][j] with matrix[j][i].
2. Reverse Each Row: Reverse the elements in each row.

Python Code #

def rotate(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()

    return matrix

# 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]]

Time Complexity: #

• O(n^2): Transposing the matrix takes O(n^2) time and so does reversing each row.

Space Complexity: #

• O(1): The rotation is done in place, so no additional space is required.