Rotate Image - C Solution

1. Introduction

In this blog post, we explore a matrix manipulation problem in C programming: rotating an n x n 2D matrix (representing an image) by 90 degrees clockwise. This problem is a common challenge in image processing and tests one's understanding of array manipulation and in-place operations.

Problem

Given an n x n 2D matrix, the task is to rotate the matrix by 90 degrees clockwise. The rotation must be done in place, meaning the original matrix must be modified directly without using an additional matrix for the rotation.

2. Solution Steps

1. Transpose the matrix: Swap matrix[i][j] with matrix[j][i].

2. Reverse each row of the transposed matrix.

3. The combination of these two operations results in a 90-degree clockwise rotation.

3. Code Program

#include <stdio.h>

// Function to transpose a matrix
void transpose(int n, int matrix[][n]) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}

// Function to reverse the rows of the matrix
void reverseRows(int n, int matrix[][n]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0, k = n - 1; j < k; j++, k--) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[i][k];
            matrix[i][k] = temp;
        }
    }
}

// Function to rotate the matrix 90 degrees clockwise
void rotate(int n, int matrix[][n]) {
    transpose(n, matrix);  // Step 1: Transpose the matrix
    reverseRows(n, matrix); // Step 2: Reverse each row
}

// Main function to demonstrate rotate function
int main() {
    int n = 3; // Size of the matrix
    int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; // Example matrix

    rotate(n, matrix); // Rotate the matrix

    // Print the rotated matrix
    printf("Output:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }

    return 0;
}

Output:

7 4 1
8 5 2
9 6 3

Explanation:

The program first transposes the given matrix, which involves swapping elements across the diagonal.

Then, it reverses each row of the transposed matrix. These two operations combined result in a 90-degree clockwise rotation of the matrix. 

In the example, the original matrix [[1, 2, 3], [4, 5, 6], [7, 8, 9]] is transformed into [[7, 4, 1], [8, 5, 2], [9, 6, 3]] by these operations. 

This approach efficiently rotates the matrix in place without needing additional memory for a separate matrix.


Comments