Master 90-Degree Matrix Rotation for Competitive Programming

Matrix rotations are a fundamental problem in computer science, often encountered in image processing, gaming, and algorithm challenges. Rotating a matrix by 90 degrees clockwise or counterclockwise involves rearranging the matrix elements while maintaining their relative positions. In this blog, we will discuss different ways to rotate a matrix by 90 degrees, including in-place and auxiliary matrix solutions. We will also explore real-world applications and provide Python code for practical implementation.

---

What Does Rotating a Matrix by 90 Degrees Mean?

When we rotate a matrix by 90 degrees:

• Clockwise Rotation: Elements in the top row move to the right column.
• Counterclockwise Rotation: Elements in the top row move to the left column.

For example, rotating the matrix below by 90 degrees clockwise:

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

Clockwise Rotation:
7  4  1  
8  5  2  
9  6  3

---

Approaches to Rotate a Matrix by 90 Degrees

1. Using an Auxiliary Matrix

This approach involves creating a new matrix to store the rotated elements.

Algorithm:

1. Create an empty matrix with the same size as the input matrix.
2. Copy elements from the original matrix to the new one in rotated positions.
3. Return the new matrix as the result.

Code for Clockwise Rotation Using an Auxiliary Matrix

def rotate_matrix_aux(matrix):
    n = len(matrix)
    rotated = [[0] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            rotated[j][n - i - 1] = matrix[i][j]

    return rotated

# Example
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
result = rotate_matrix_aux(matrix)
for row in result:
    print(row)

Output:

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

Time Complexity: O(n²)
Space Complexity: O(n²) (due to the auxiliary matrix)

---

2. In-Place Rotation

In this optimized approach, we rotate the matrix in-place, meaning no extra space is required.

Algorithm:

1. Transpose the matrix: Swap elements across the diagonal.
2. Reverse each row: This completes the clockwise rotation.

Code for In-Place Rotation (Clockwise)

def rotate_matrix_in_place(matrix):
    n = len(matrix)

    # Transpose the matrix
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

    # Reverse each row
    for i in range(n):
        matrix[i].reverse()

# Example
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
rotate_matrix_in_place(matrix)
for row in matrix:
    print(row)

Output:

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

Time Complexity: O(n²)
Space Complexity: O(1) (in-place rotation)

---

Real-World Applications of Matrix Rotation

1. Image Processing:
   Rotating images involves manipulating pixel grids, which are represented as matrices.
2. Game Development:
   Games with grid-based elements (like Tetris) rely heavily on matrix rotations for piece movement.
3. Robotics and Computer Vision:
   Matrix transformations are used to rotate 2D views captured by cameras or sensors.
4. Mathematics and Physics Simulations:
   Matrix operations, including rotations, are essential for transformations in vector spaces.

---

Rotating a Matrix by 90 Degrees Counterclockwise

For counterclockwise rotation, the process is similar, but instead of reversing rows, we reverse columns after transposing the matrix.

Code for Counterclockwise Rotation (In-Place)

def rotate_matrix_counterclockwise(matrix):
    n = len(matrix)

    # Transpose the matrix
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

    # Reverse each column
    for j in range(n):
        for i in range(n // 2):
            matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]

# Example
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
rotate_matrix_counterclockwise(matrix)
for row in matrix:
    print(row)

Output:

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

---

FAQs

1. What is the difference between clockwise and counterclockwise rotation?
   In clockwise rotation, elements move to the right column, while in counterclockwise rotation, they move to the left column.
2. Can we rotate non-square matrices?
   The algorithms discussed work primarily for square matrices. For non-square matrices, additional handling is required to manage dimensions.
3. What are the time and space complexities?
   Both the auxiliary and in-place methods have a time complexity of O(n²). The in-place method, however, has a space complexity of O(1).

---

Rotating a matrix by 90 degrees is an essential operation in many applications, from image processing to game development. In this blog, we explored two approaches—using an auxiliary matrix and performing in-place rotation. While the auxiliary matrix approach is easier to implement, the in-place method is more space-efficient and ideal for large datasets.

Mastering matrix rotations will give you a solid understanding of matrix manipulations and help you tackle competitive programming challenges and real-world projects effectively.

---

Outbound links –

• Matrix Rotations on GeeksforGeeks
• Matrix Manipulation Problems on LeetCode

Let me know if you need further insights or any additional examples!

Read More …

Array Sorting: Comprehensive Guide, Techniques, and LeetCode Solutions – https://kamleshsingad.com/wp-admin/post.php?post=5110&action=edit

Bulb Switcher III: A Comprehensive Guide and Solution – https://kamleshsingad.com/wp-admin/post.php?post=5096&action=edit

Minimize the Maximum Difference Between Heights – An Efficient Solution and Approach – https://kamleshsingad.com/wp-admin/post.php?post=5115&action=edit