Rotate matrix by 90 degrees

Problem Statement

Given an n x n square matrix, rotate it by 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]]

Approach 1: Using Extra Space

Intuition

Create a new matrix and place elements at their rotated positions. For 90° clockwise rotation: element at (i, j) moves to (j, n-1-i).

Algorithm

1. Create a new n x n matrix
2. For each element at (i, j), place it at (j, n-1-i) in new matrix
3. Copy back to original matrix

public class Solution {
    public void rotateBrute(int[][] matrix) {
        int n = matrix.length;
        int[][] rotated = new int[n][n];
        
        // Place elements in rotated positions
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                rotated[j][n - 1 - i] = matrix[i][j];
            }
        }
        
        // Copy back
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = rotated[i][j];
            }
        }
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - Visit each element twice
• Space Complexity: O(n^2) - Extra matrix for rotation

Approach 2: Transpose + Reverse (Optimal)

Intuition

90° clockwise rotation = Transpose + Reverse each row

• Transpose: Swap element at (i, j) with (j, i)
• Reverse rows: Reverse each row

This works because:

• Transpose changes (i, j) to (j, i)
• Reversing row changes (j, i) to (j, n-1-i)
• Combined: (i, j) → (j, n-1-i), which is 90° clockwise rotation

Algorithm

1. Transpose the matrix (swap across main diagonal)
2. Reverse each row

public 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++) {
            int left = 0, right = n - 1;
            while (left < right) {
                int temp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = temp;
                left++;
                right--;
            }
        }
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - Transpose O(n^2) + Reverse O(n^2)
• Space Complexity: O(1) - In-place rotation

Approach 3: Layer by Layer (Cycle Approach)

Intuition

Rotate elements in groups of 4, layer by layer from outside to inside. For each layer, we rotate four corners at a time.

Algorithm

1. Process each layer from outside to inside
2. For each layer, process each group of 4 elements
3. Rotate the 4 elements in cycle

public class Solution {
    public void rotateLayerByLayer(int[][] matrix) {
        int n = matrix.length;
        
        // Process each layer
        for (int layer = 0; layer < n / 2; layer++) {
            int first = layer;
            int last = n - 1 - layer;
            
            for (int i = first; i < last; i++) {
                int offset = i - first;
                
                // Save top
                int top = matrix[first][i];
                
                // Left -> Top
                matrix[first][i] = matrix[last - offset][first];
                
                // Bottom -> Left
                matrix[last - offset][first] = matrix[last][last - offset];
                
                // Right -> Bottom
                matrix[last][last - offset] = matrix[i][last];
                
                // Top -> Right
                matrix[i][last] = top;
            }
        }
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - Each element is moved exactly once
• Space Complexity: O(1) - Only using one temp variable

Rotation Variants

90° Counter-Clockwise (Anti-Clockwise)

180° Rotation

Transformation Summary

| Rotation | Steps | |----------|-------| | 90° CW | Transpose → Reverse rows | | 90° CCW | Reverse rows → Transpose | | 180° | Reverse rows → Reverse each row | | Vertical flip | Reverse matrix (swap rows) | | Horizontal flip | Reverse each row |

Key Takeaways

1. Transpose + Reverse is the most intuitive in-place approach
2. For 90° clockwise: Transpose, then reverse each row
3. For 90° counter-clockwise: Reverse each row, then transpose
4. The layer-by-layer approach directly moves elements in cycles
5. All approaches have O(n^2) time but differ in space complexity
6. The transformation composition insight is powerful for any rotation angle
7. For non-square matrices, rotation requires extra space