Vansh Aggarwal

Posted on May 4

LeetCode Solution: 48. Rotate Image

#leetcode #dsa #programming #tutorial

Spin That Image! Rotating a 2D Matrix Like a Pro (LeetCode #48)

Hey fellow coders and aspiring problem-solvers! 👋 Vansh here, diving into another classic LeetCode challenge that's more about visual thinking than complex algorithms. Today, we're tackling problem #48: Rotate Image.

This one is fantastic because it pushes us to think in-place, meaning we can't just create a new matrix and copy rotated values. We have to be clever and modify the original! Ready to give your matrix a spin? Let's go!

Understanding the Challenge: Rotate That Image!

You're given a square 2D matrix (think of it like a grid or an image made of pixels). Your task is to rotate this "image" by 90 degrees clockwise.

The catch? You must do it in-place. No creating a brand new matrix to store the result. You have to transform the given matrix directly.

Let's look at an example to make it super clear:

Example 1: A simple 3x3 matrix

Input:

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

Imagine physically turning this piece of paper 90 degrees clockwise.

Output:

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

Notice how 1 (top-left) moves to (0, 2) (top-right of new matrix), 3 (top-right) moves to (2, 2) (bottom-right of new matrix), and so on.

The "Aha!" Moment: Two Simple Steps to Rotation

Rotating an image 90 degrees clockwise in-place might seem tricky at first. If you try to move elements one by one, you'll quickly realize you need to store temporary values to avoid overwriting numbers you still need. That can get messy fast!

But what if we could break down this complex rotation into simpler, more intuitive transformations?

The "aha!" moment comes when you realize that a 90-degree clockwise rotation can be achieved by two fundamental operations:

Transpose the matrix: This means swapping elements across its main diagonal. matrix[i][j] becomes matrix[j][i].
Reverse each row: After transposing, each row needs to be reversed to get the final clockwise rotation.

Let's visualize this with our 3x3 example:

Original Matrix:

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

Step 1: Transpose (Swap (0,1) with (1,0), (0,2) with (2,0), (1,2) with (2,1))

[[1, 4, 7],   <-- 1 (0,0) stays, 2 (0,1) swapped with 4 (1,0), 3 (0,2) swapped with 7 (2,0)
 [2, 5, 8],   <-- 5 (1,1) stays, 6 (1,2) swapped with 8 (2,1)
 [3, 6, 9]]   <-- 9 (2,2) stays

Step 2: Reverse Each Row
Row 0: [1, 4, 7] becomes [7, 4, 1]
Row 1: [2, 5, 8] becomes [8, 5, 2]
Row 2: [3, 6, 9] becomes [9, 6, 3]

Final Rotated Matrix:

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

Voila! This matches our desired output. This two-step process does the job perfectly, and it's all done in-place!

The Step-by-Step Approach

Let's break down how to implement these two steps efficiently in code.

Step 1: Transposing the Matrix

To transpose a matrix in-place, we iterate through the upper triangle of the matrix and swap matrix[i][j] with matrix[j][i]. We only need to consider j starting from i + 1 to avoid:

Swapping elements twice (e.g., swapping (0,1) with (1,0) and then (1,0) with (0,1) again would revert the change).
Swapping elements on the main diagonal with themselves (e.g., (0,0) with (0,0)).

Algorithm for Transposition:

Get the size of the matrix, n.
Loop with i from 0 to n-1 (for rows).
Inside this, loop with j from i+1 to n-1 (for columns, starting from i+1).
Swap matrix[i][j] with matrix[j][i].

Step 2: Reversing Each Row

After transposition, each individual row needs to be reversed. This is a straightforward operation.

Algorithm for Reversing Rows:

Loop with i from 0 to n-1 (for each row).
For each matrix[i], use a reverse function (most languages have one built-in for containers like vectors or arrays) to reverse its elements. If not, you can implement a simple two-pointer swap from start and end of the row.

And that's it! These two operations combined give you the 90-degree clockwise rotation, all without using extra space.

The Code (C++)

Here's the C++ implementation of this elegant solution:

#include <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
        // Iterate through the upper triangle (j starts from i+1)
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                // Swap matrix[i][j] with matrix[j][i]
                std::swap(matrix[i][j], matrix[j][i]);
            }
        }

        // Step 2: Reverse each row
        // Iterate through each row and reverse its elements
        for (int i = 0; i < n; ++i) {
            std::reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

Complexity Analysis

Time Complexity:
- Transposition: We have a nested loop. The outer loop runs n times, and the inner loop runs approximately n/2 times on average (j goes from i+1 to n-1). In total, we perform (n-1) + (n-2) + ... + 1 = n*(n-1)/2 swaps. This is proportional to n^2. So, it's O(n^2).
- Reversing Rows: We iterate through n rows. For each row, we iterate through its n elements to reverse them. This also takes O(n * n) = O(n^2) time.
- Overall: The dominant factor is n^2. Therefore, the total time complexity is O(n^2), where n is the dimension of the square matrix.
Space Complexity:
- We are performing all operations directly on the input matrix without allocating any additional matrices or significant data structures. The std::swap and std::reverse operations work in-place.
- Therefore, the space complexity is O(1) (constant space).

Key Takeaways

In-Place Challenges: Problems requiring "in-place" modification often hint at clever manipulations like swapping or using existing memory efficiently.
Decomposition: Complex transformations (like 90-degree rotation) can often be broken down into simpler, sequential operations (like transpose + reverse).
Visual Thinking: Drawing out the matrix and how elements move is incredibly helpful for problems involving 2D arrays.
Standard Library Functions: Don't forget powerful standard library functions like std::swap and std::reverse in C++ (or equivalent in other languages) – they can simplify your code and often are highly optimized.

I hope this breakdown made the "Rotate Image" problem feel less daunting and more like a fun puzzle! Happy coding, and keep spinning those matrices!

Author Account: Vansh2710
Time Published: 2026-05-04 12:03:48

DEV Community