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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Rotate Image

Number: 48

Difficulty: Medium

Paid? No

Companies: Google, Meta, Cisco, Microsoft, Amazon, Uber, J.P. Morgan, Bloomberg, Zoho, Roblox, IBM, Infosys, Tinkoff, Capital One, Apple, Salesforce, Walmart Labs, Accenture, Adobe, Yahoo, Nvidia, Oracle, ZScaler, Citadel, AMD

Problem Description

Given an n x n 2D matrix representing an image, rotate the image by 90 degrees clockwise in-place without allocating an additional matrix.

Key Insights

  • The rotation can be achieved in two steps: first transpose the matrix and then reverse each row.
  • Transposing the matrix swaps matrix[i][j] with matrix[j][i], converting rows into columns.
  • Reversing each row post-transposition yields the desired clockwise rotation.
  • This approach works in-place with O(1) extra space.

Space and Time Complexity

Time Complexity: O(n^2) since every element is processed during the transpose and row reversal. Space Complexity: O(1) as the operations are performed in-place without extra data structures.

Solution

The solution leverages a two-step in-place transformation:

  1. Transpose the matrix: Iterate through the matrix and swap each element (i, j) with element (j, i) for j >= i.
  2. Reverse each row: After the transpose, each row is reversed to rotate the matrix 90 degrees clockwise. The key trick is to realize that a transpose followed by a reverse of each row achieves the rotation without needing extra space.

Code Solutions

def rotate(matrix):
    n = len(matrix)
    # Transpose the matrix by swapping elements across the diagonal
    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 to complete the clockwise rotation
    for i in range(n):
        matrix[i].reverse()

# Example usage:
matrix = [[1,2,3],[4,5,6],[7,8,9]]
rotate(matrix)
print(matrix)  # Outputs: [[7,4,1],[8,5,2],[9,6,3]]
← Back to All Questions