Prerequisites: Matrix, Array/Vector, Sorting etc.
Problem: Given an N x N square matrix, rotate it 90 degrees clockwise .
Solution Approach:
The solution uses two step manipulation on given input matrix.
Step 1: Reverse Rows (Vertical Flip)
Reversing the rows of a matrix effectively flips the matrix vertically. Let’s denote the original matrix as A and the matrix after reversing the rows as A’. Consider an example with a 3x3 matrix:
Original Matrix (A):
1 2 3
4 5 6
7 8 9
After reversing rows:
7 8 9
4 5 6
1 2 3
As observed, the rows have been reversed, resulting in a vertical flip of the matrix.
Step 2: Transpose
Transposing a matrix involves swapping elements across the diagonal (row-column index exchange). Let’s denote the transposed matrix of A’ as A’'.
Original Matrix (A’):
7 8 9
4 5 6
1 2 3
After transposing:
7 4 1
8 5 2
9 6 3
The rows have become columns and vice versa. This operation effectively rotates the matrix 90 degrees counterclockwise.
Combining Step 1 and Step 2:
When we combine reversing the rows and transposing the matrix, we first achieve a vertical flip (Step 1) and then rotate the matrix 90 degrees counterclockwise (Step 2).
Original Matrix (A):
1 2 3
4 5 6
7 8 9
After Step 1 (Reversing Rows):
7 8 9
4 5 6
1 2 3
After Step 2 (Transposing):
7 4 1
8 5 2
9 6 3
The resulting matrix is the original matrix rotated 90 degrees clockwise.
Therefore, combining Step 1 and Step 2 in the provided algorithm rotates the matrix 90 degrees clockwise.
Time Complexity:
- Let N be the number of rows (or columns) in the square matrix.
- Reversing Rows: O(N) to reverse N rows.
- Transpose: O(N^2) to traverse and swap elements in the upper triangular part of the matrix.
- Overall time complexity: O(N^2)
Space Complexity:
- Since the rotation is performed in-place, the space complexity is O(1), as no additional space is used apart from some constant space for variables used in the algorithm.