algoadvance

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

Clarifying Questions

  1. Can you confirm the constraints on n? Is there a minimum or maximum size for the matrix?
  2. Is it guaranteed that the matrix contains only integers?

Strategy

To solve the problem in-place, we can utilize the following steps:

  1. Transpose the Matrix: Convert all rows to columns.
  2. Reverse each Row: Reverse the individual rows to achieve the desired 90-degree clockwise rotation.

Steps:

  1. Transpose: Swap matrix[i][j] with matrix[j][i] for all i < j.
  2. Reverse Rows: Reverse each row individually.

Here’s the code that implements the above approach:

Code

def rotate(matrix):
    n = len(matrix)
    
    # 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]
    
    # Reverse each row
    for i in range(n):
        matrix[i].reverse()

# Test example
matrix1 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate(matrix1)
print(matrix1)  # Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

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

Time Complexity

The time complexity of this solution is O(n^2) because:

  1. Transposing the matrix involves iterating over each element above the diagonal once, which takes O(n^2/2) = O(n^2).
  2. Reversing each row is O(n) for each row, leading to an additional O(n^2) for n rows.

Thus, the overall time complexity is O(n^2).

Space Complexity

The space complexity is O(1) since we are rotating the matrix in-place and not using any extra space apart from variables.

Try our interview co-pilot at AlgoAdvance.com