We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Rotate Image

Difficulty: Medium

Problem Description

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.

Key Insights

  • The rotation can be achieved by transposing the matrix and then reversing each row.
  • Transposing involves flipping the matrix over its diagonal, converting rows to columns.
  • After transposing, reversing each row gives the desired 90-degree clockwise rotation.

Space and Time Complexity

Time Complexity: O(n^2) - We traverse each element of the matrix once. Space Complexity: O(1) - The operation is done in-place without using additional space.

Solution

To rotate the image in-place, we can follow these steps:

  1. Transpose the matrix: For each element at position (i, j), swap it with the element at position (j, i).
  2. Reverse each row of the transposed matrix to achieve the clockwise rotation.

This method effectively modifies the original matrix without requiring extra space.

Code Solutions

def rotate(matrix):
    n = len(matrix)
    # Step 1: Transpose the matrix
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    
    # Step 2: Reverse each row
    for i in range(n):
        matrix[i].reverse()
← Back to All Questions