LeetCode Solution 48 - Rotate Image

 Problem Statement

You are given an n x n 2D matrix representing an image. Rotate the image 90 degrees (clockwise) in-place.

Example:

Input:

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

Output:

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

Constraints:

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

---

Optimal Approach: Transpose & Reverse

Explanation:

1. Transpose the matrix: Swap matrix[i][j] with matrix[j][i] for i < j.
2. Reverse each row: Swap elements symmetrically along the middle column.

C++ Implementation (LeetCode-Compatible)

class Solution {
public:
    void rotate(vector<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++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        // Reverse each row
        for (int i = 0; i < n; i++) {
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

Step-by-Step Explanation

• Transpose the matrix:
  • Swap elements across the diagonal (matrix[i][j] <-> matrix[j][i]).
• Reverse each row:
  • Reverse every row to complete the 90-degree rotation.

---

Dry Run Example:

Input:

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

Execution Steps:

Step	Matrix State
Transpose	[ [1,4,7], [2,5,8], [3,6,9] ]
Reverse Rows	[ [7,4,1], [8,5,2], [9,6,3] ]

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not Optimal?
Brute Force (New Matrix)	O(N^2)	O(N^2)	Extra space used
Layer-wise Rotation	O(N^2)	O(1)	More swaps, less intuitive

Layer-wise Rotation (Alternative)

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int layer = 0; layer < n / 2; layer++) {
            int first = layer, last = n - 1 - layer;
            for (int i = first; i < last; i++) {
                int offset = i - first;
                int top = matrix[first][i];
                matrix[first][i] = matrix[last - offset][first];
                matrix[last - offset][first] = matrix[last][last - offset];
                matrix[last][last - offset] = matrix[i][last];
                matrix[i][last] = top;
            }
        }
    }
};

Why is Layer-wise Rotation Less Optimal?

• More swap operations than transpose + reverse.
• Harder to understand and implement correctly.

---

Best Solution & Why?

Approach	Time Complexity	Space Complexity	Best Choice?
Transpose & Reverse	O(N^2)	O(1)	✅ Best (intuitive & efficient)
Layer-wise Rotation	O(N^2)	O(1)	❌ More swaps
Brute Force (Extra Matrix)	O(N^2)	O(N^2)	❌ Uses extra memory

Why is Transpose & Reverse Best?

• Linear Time Complexity (O(N^2)) ✅
• Constant Space (O(1)) ✅
• Simpler & More Intuitive ✅

---

Conclusion

• Best Solution: Transpose & Reverse.
• Why? Efficient O(N^2) time, O(1) space.
• Alternative Solutions: Layer-wise swaps (more steps), Brute force (extra space).

Practice More:

• Spiral Matrix
• Set Matrix Zeroes
• Rotate Image (Anti-clockwise)