algoadvance

Leetcode 48. Rotate Image

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.

Constraints:

Clarifying Questions

  1. Can we use extra space to store intermediate results?
    • No, the problem explicitly states to rotate the matrix in-place without using extra space for another matrix.
  2. Is the input matrix always square?
    • Yes, the input matrix is always n x n.
  3. What is the range of the size of the matrix n?
    • The size n ranges from 1 to 20.

Strategy

To achieve the in-place rotation of the matrix:

  1. Transpose the matrix: Convert rows to columns.
  2. Reverse each row: To get the required 90-degree clockwise rotation.

Here are the steps in detail:

  1. Transpose the matrix:
    • Swap matrix[i][j] with matrix[j][i] for each element in the upper triangle of the matrix (i.e., where i < j).
  2. Reverse each row:
    • For each row in the matrix, reverse the row.

Example:

Given matrix:

[
 [1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]
]

Transpose the matrix:

[
 [1, 4, 7],
 [2, 5, 8],
 [3, 6, 9]
]

Reverse each row:

[
 [7, 4, 1],
 [8, 5, 2],
 [9, 6, 3]
]

Code

#include <vector>
#include <algorithm>

void rotate(std::vector<std::vector<int>>& matrix) {
    int n = matrix.size();
    
    // Transpose the matrix
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            std::swap(matrix[i][j], matrix[j][i]);
        }
    }
    
    // Reverse each row
    for (int i = 0; i < n; ++i) {
        std::reverse(matrix[i].begin(), matrix[i].end());
    }
}

Time Complexity

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

Space Complexity

Since we are performing the operation in-place and not allocating additional space for another matrix, the space complexity is O(1) (excluding the space required for the input matrix itself).

Feel free to ask if you have any questions or need further clarification.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI