Rotate image matrix problem in C#

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

  1. 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).

  2. 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

  1. Matrix Declaration: The function Rotate takes a jagged array (int[][] matrix) as an input, representing the square matrix.

  2. 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.
  3. Reverse Each Row:

    • After transposing, we use Array.Reverse() to reverse each row of the matrix. This step completes the rotation.

Example

Given the input matrix:

1  2  3
4  5  6
7  8  9
  1. Transpose:
1  4  7
2  5  8
3  6  9
  1. 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#.