Rotate Matrix

Problem Overview

The problem "Rotate Image" from LeetCode is a popular question that tests your understanding of arrays and matrix manipulation. The task requires you to rotate a given n x n 2D matrix representing an image by 90 degrees clockwise, in place.

Understanding the Problem

Given an n x n matrix, you are required to rotate it 90 degrees clockwise. This transformation involves rearranging the elements in the matrix without using any extra space for another matrix. For example, consider the following matrix:

Matrix:
1 2 3
4 5 6
7 8 9

Rotate 90 degrees clockwise:
7 4 1
8 5 2
9 6 3

Key DSA Concepts and Theory

To address this problem, we focus on matrix manipulation and in-place transformations. Let's discuss some key concepts:

1. Matrix Transpose: Transposing a matrix involves flipping it over its diagonal. For example, the transpose of the above matrix is:

   Original Matrix:
   1 2 3
   4 5 6
   7 8 9
   
   Transpose:
   1 4 7
   2 5 8
   3 6 9
   

2. Reverse Rows: Once we have the transposed matrix, we can achieve a 90-degree clockwise rotation by reversing the elements of each row.

These two operations can be executed directly on the input matrix, addressing the problem's constraint regarding in-place transformations.

Solution Approach

To rotate the image by 90 degrees clockwise:

Step-by-Step Solution

1. Transpose the Matrix: Swap matrix[i][j] with matrix[j][i] for all i and j. This step will make rows into columns.

2. Reverse Each Row: For each row in the transposed matrix, swap the elements, treating the row as a one-dimensional array.

Following this approach, the matrix will be rotated 90 degrees clockwise.

C++ Code

#include <vector>

void rotate(std::vector<std::vector<int>>& matrix) {
    int n = matrix.size();
    // Transpose the matrix
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            std::swap(matrix[i][j], matrix[j][i]);
        }
    }
    // Reverse each row
    for (int i = 0; i < n; ++i) {
        std::reverse(matrix[i].begin(), matrix[i].end());
    }
}

Java Code

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // Transpose the matrix
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        // Reverse each row
        for (int i = 0; i < n; i++) {
            int start = 0, end = n - 1;
            while (start < end) {
                int temp = matrix[i][start];
                matrix[i][start] = matrix[i][end];
                matrix[i][end] = temp;
                start++;
                end--;
            }
        }
    }
}

Time and Space Complexity Analysis

• Time Complexity: The solution is efficient with a time complexity of O(n^2) as we iterate through the matrix twice (once for transposing and once for reversing rows).

• Space Complexity: Since the rotation is done in place with no additional data structures, the space complexity is O(1).

Common Mistakes to Avoid

1. Confusion Between Transpose and Rotate: Ensure you understand that transposing and rotating are separate operations. Transpose swaps rows with columns, while rotating requires a subsequent reversal of the rows.

2. In-Place Requirement: Avoid using additional matrices to store the rotated version, as this goes against the in-place constraint of the problem.

Similar Problems on LeetCode

1. Flip Image (LeetCode 832)
2. Spiral Matrix (LeetCode 54)
3. Transpose Matrix (LeetCode 867)

Additional Resources and References

• Matrix Rotation Concept: For visual learners, understanding matrix rotation concepts through graphical representations can be beneficial.
• In-place Algorithm Explanation: Look into algorithm efficiency and memory usage further to enhance your understanding of in-place operations.
• CS Algorithms Resources: Websites like GeeksforGeeks and educational YouTube channels provide valuable tutorials on matrix manipulation and related algorithms.