Algorithm-Day20-Rotate-Image-lc-48

🧩 Problem Description

You are given an n x n 2D matrix representing an image. Rotate the image 90 degrees clockwise.

You must rotate the image in place.

Example:

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

---

💡 Brute Force Approach (Not Allowed)

• Create a new matrix and write rotated values into it.
• ❌ Uses O(n²) extra space, violates “in-place” requirement.

---

💡 Optimal Approach: Transpose + Reverse

✨ Key Idea

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

This combination achieves a 90-degree clockwise rotation in place.

---

🔢 Java Code

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        // Step 1: Transpose
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // Step 2: Reverse each row
        for (int i = 0; i < n; i++) {
            reverseRow(matrix[i]);
        }
    }

    private void reverseRow(int[] row) {
        int left = 0, right = row.length - 1;
        while (left < right) {
            int temp = row[left];
            row[left] = row[right];
            row[right] = temp;
            left++;
            right--;
        }
    }
}

---

⏱ Time and Space Complexity

• Time Complexity: O(n²)
  Each element is processed twice (transpose + reverse).
• Space Complexity: O(1)
  Fully in-place.

---

✍️ Summary

• The transpose + reverse method is an elegant solution for in-place rotation problems.
• Remember:
  • Clockwise → transpose + reverse rows
  • Counterclockwise → transpose + reverse columns
• This is a core pattern in matrix transformation problems.

Mastering in-place matrix tricks helps with both interviews and real-world image manipulation tasks.