LeetCode Solution: 48. Rotate Image

Matrix Makeover: Rotating Images 90 Degrees In-Place with C++

Hey LeetCoders and aspiring problem-solvers! 👋 Vansh2710 here, ready to demystify another classic LeetCode problem that might seem tricky at first glance, but unveils an elegant two-step solution. Today, we're diving into problem 48: Rotate Image.

Get ready to spin some matrices! 🔄

---

The Problem: Spin That Image!

You're given an n x n 2D matrix, which you can think of as a square image made of pixels (where each pixel has a numerical value). Your task is to rotate this "image" by 90 degrees clockwise.

Sounds simple, right? Here's the catch:

• You must do this rotation in-place. This means you can't create a brand new matrix, fill it with rotated values, and then return it. You have to modify the original matrix directly.
• DO NOT allocate another 2D matrix.

Let's look at an example to really nail down what we're aiming for:

Input:

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

Imagine this as:

1 2 3  <-- Top row
4 5 6
7 8 9  <-- Bottom row

Output:

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

After a 90-degree clockwise rotation, it should look like:

7 4 1
8 5 2
9 6 3

Notice how the 1 (top-left) moved to 3's old spot (top-right of the rotated matrix, which is bottom-right of the original), but it actually ends up in [0][2] position of the result. Wait, no, 1 from [0][0] moves to [0][2] in the output [[7,4,1],...]. Let's clarify the coordinate transformation for a moment:

• Original (row, col) becomes (col, n - 1 - row) in the new matrix.
  • 1 at (0,0) goes to (0, 3-1-0) = (0,2) in the output. Output matrix[0][2] is 1.
  • 3 at (0,2) goes to (2, 3-1-0) = (2,2) in the output. Output matrix[2][2] is 3.
  • 7 at (2,0) goes to (0, 3-1-2) = (0,0) in the output. Output matrix[0][0] is 7.

This direct mapping approach is hard to do in-place without overwriting values you still need. So, what's the trick? 🤔

---

The Intuition: A Two-Step Dance!

The key to solving this problem efficiently and in-place lies in breaking down the complex 90-degree rotation into two simpler, sequential transformations. This is a classic trick for matrix manipulations!

Think about what happens when you rotate something 90 degrees clockwise:

1. The rows become columns, and columns become rows. This sounds a lot like transposing a matrix.
2. Then, the order within those new rows/columns seems reversed or mirrored.

Let's try this with our example: [[1,2,3],[4,5,6],[7,8,9]]

Step 1: Transpose the Matrix
Transposing means swapping matrix[i][j] with matrix[j][i]. It's like flipping the matrix along its main diagonal (top-left to bottom-right).

Original:

1 2 3
4 5 6
7 8 9

After Transposing (swapping (0,1) with (1,0), (0,2) with (2,0), (1,2) with (2,1)):

1 4 7
2 5 8
3 6 9

• 2 and 4 swapped.
• 3 and 7 swapped.
• 6 and 8 swapped.
• 1, 5, 9 stayed in place (they are on the main diagonal).

Does this look like our desired output? Not yet! But we're closer. Notice the numbers are somewhat "lined up".

Step 2: Reverse Each Row
Now, let's take this transposed matrix and reverse the elements within each row.

Transposed Matrix:

1 4 7
2 5 8
3 6 9

Reverse Row 0 [1,4,7] -> [7,4,1]
Reverse Row 1 [2,5,8] -> [8,5,2]
Reverse Row 2 [3,6,9] -> [9,6,3]

Final Result:

7 4 1
8 5 2
9 6 3

Aha! This is exactly the output we wanted! 🎉
This two-step process – Transpose then Reverse Rows – is the elegant, in-place solution.

---

The Approach: Walking Through the Logic

Armed with our intuition, let's break down the exact steps to implement this:

1. Get the size: First, find the dimension n of the square matrix. n = matrix.size().

2. Transpose the Matrix:

   • We need nested loops to iterate through the matrix elements.
   • The outer loop i will go from 0 to n-1 (for rows).
   • The inner loop j will go from i+1 to n-1 (for columns).
   • Why j starts at i+1? To avoid two things:
     • Swapping an element with itself (matrix[i][i] with matrix[i][i]).
     • Swapping pairs twice (e.g., swapping matrix[0][1] with matrix[1][0], and then later swapping matrix[1][0] with matrix[0][1] again, which undoes the first swap). By starting j from i+1, we only visit the "upper triangle" of the matrix, ensuring each unique pair is swapped exactly once.
   • Inside the inner loop, perform the swap: swap(matrix[i][j], matrix[j][i]).

3. Reverse Each Row:

   • Now, we need another loop to iterate through each row of the matrix.
   • The loop i will go from 0 to n-1.
   • For each row matrix[i], use a reverse function (like std::reverse in C++) to reverse all its elements.

And that's it! Two simple loops, two clear operations, and your matrix is rotated!

---

The Code: Bringing it to Life

Here's the C++ implementation based on our approach:

#include <vector>     // Required for std::vector
#include <algorithm>  // Required for std::swap and std::reverse

class Solution {
public:
    void rotate(std::vector<std::vector<int>>& matrix) {
        int n = matrix.size(); // Get the dimension of the square matrix

        // Step 1: Transpose the matrix
        // Swap elements across the main diagonal (matrix[i][j] with matrix[j][i])
        // We iterate through the upper triangle (j starts from i+1) to avoid redundant swaps
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                std::swap(matrix[i][j], matrix[j][i]);
            }
        }

        // Step 2: Reverse each row
        // After transposing, reversing each row completes the 90-degree clockwise rotation
        for (int i = 0; i < n; ++i) {
            std::reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

---

Complexity Analysis

Understanding how our solution scales with input size is crucial for competitive programming and good software design.

• Time Complexity: O(n^2)

  • The transposition step involves nested loops, where the outer loop runs n times and the inner loop runs approximately n/2 times on average (from i+1 to n-1). This results in roughly (n * (n-1))/2 operations, which simplifies to O(n^2).
  • The row reversal step involves iterating through n rows. For each row, std::reverse takes O(n) time (to reverse n elements). So, this step is also n * O(n) = O(n^2).
  • Since both steps are O(n^2), the dominant factor, the total time complexity is O(n^2). This is optimal because we have to visit every element in the n x n matrix at least once.

• Space Complexity: O(1)

  • We are modifying the matrix directly in-place. We don't use any additional data structures whose size depends on n.
  • std::swap and std::reverse might use a small, constant amount of auxiliary space for temporary variables, but this is negligible in terms of n.
  • Therefore, the auxiliary space complexity is O(1). This meets the "DO NOT allocate another 2D matrix" constraint perfectly!

---

Key Takeaways

• Decomposition is Powerful: Complex problems can often be broken down into simpler, sequential operations. For 90-degree clockwise matrix rotation, this is Transpose + Reverse Rows.
• In-place Transformations: Look for ways to manipulate data directly without extra memory. This often involves careful iteration patterns (like j = i + 1 for transposition) and using language-provided utilities (std::swap, std::reverse).
• Visualize the Changes: Drawing out small examples and tracking element movement can lead to the "aha!" moment much faster.

This problem is a fantastic introduction to matrix manipulation and in-place algorithms. Understanding this pattern will help you tackle similar problems in the future!

Happy coding! ✨

---

Authored by Vansh2710.
Published on 2026-03-28 at 22:46:29.