Lecture on Rotating a Matrix by 90 Degrees

Course Overview

• This course has 455 modules.
• Covers over 400 problems on Data Structures and Algorithms (DSA).
• By completing this course, you will be able to implement DS algorithms in any company globally.

Problem Statement: Rotate Matrix by 90 Degrees (Clockwise)

• Input: An N x N (square) matrix.
• Output: The matrix rotated by 90 degrees clockwise.
• Also known as the rotate image problem.
• Common interview question.

Brute Force Solution

1. Create a new N x N matrix to store the result.
2. Map each element in the original matrix to its appropriate position in the new matrix by following the transformation rules.
3. Observations:
   • The first row becomes the last column, the second row becomes the second last column, etc.
   • General formula: Element at position (i, j) in the original matrix is placed at (j, N-1-i) in the new matrix.

Brute Force Code

n = len(matrix)
result = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        result[j][n-1-i] = matrix[i][j]
return result

Time and Space Complexity

• Time Complexity: O(N^2)
• Space Complexity: O(N^2) (due to use of an extra matrix)

Optimized Solution (In-place)

• Goal: Solve the problem within the given matrix (without using extra space).
• Key Observations:
  • First column in reversed order becomes the first row.
  • Second column in reversed order becomes the second row, and so on.
• Steps:
  1. Transpose the matrix: Convert rows into columns.
  2. Reverse each row.

Transposing the Matrix

• Swap non-diagonal elements: matrix[i][j] = matrix[j][i]
• Indices transformation: (i, j) -> (j, i)

Reversing each Row

• Reverse elements in each row using two-pointer approach.

Optimized Code

def rotate(matrix):
    n = len(matrix)
    # Step 1: Transpose the matrix
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Step 2: Reverse each row
    for i in range(n):
        matrix[i].reverse()

Time and Space Complexity

• Time Complexity: O(N^2)
• Space Complexity: O(1) (In-place transformation)

Conclusion

• Brute Force: Clear but inefficient due to extra space.
• Optimized Approach: Effective and follows in-place constraints.
• Key Steps: Transpose and Reverse Each Row.