Rotating a matrix is a common problem, often encountered in coding interviews and algorithm exercises. The problem usually involves rotating a square matrix (2D array) 90 degrees clockwise. Here’s a step-by-step explanation along with a C# implementation.
Problem Statement
Given a square matrix (n x n), you need to rotate it 90 degrees clockwise in place.
Steps to Rotate the Matrix
-
Transpose the Matrix: This involves swapping the rows and columns. For a matrix element at position
(i, j)
, it gets swapped with the element at(j, i)
. -
Reverse Each Row: After transposing, you reverse each row to achieve the 90-degree rotation.
C# Implementation
Here’s a C# function that demonstrates this approach:
public class MatrixRotation
{
public void Rotate(int[][] matrix)
{
int n = matrix.Length;
// Step 1: Transpose the matrix
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
// Swap elements at (i, j) and (j, i)
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++)
{
Array.Reverse(matrix[i]);
}
}
}
Explanation of the Code
-
Matrix Declaration: The function
Rotate
takes a jagged array (int[][] matrix
) as an input, representing the square matrix. -
Transpose the Matrix:
- The outer loop iterates through the rows, and the inner loop starts from
i + 1
to avoid swapping elements back. - We swap elements in pairs to transpose the matrix.
- The outer loop iterates through the rows, and the inner loop starts from
-
Reverse Each Row:
- After transposing, we use
Array.Reverse()
to reverse each row of the matrix. This step completes the rotation.
- After transposing, we use
Example
Given the input matrix:
1 2 3
4 5 6
7 8 9
- Transpose:
1 4 7
2 5 8
3 6 9
- Reverse Each Row:
7 4 1
8 5 2
9 6 3
This results in the matrix being rotated 90 degrees clockwise.
Complexity
- Time Complexity: O(n²), where n is the number of rows (or columns) in the matrix.
- Space Complexity: O(1) for in-place rotation, since we are not using any additional data structures that depend on the input size.
This method is efficient and straightforward for rotating a matrix in C#.