Rotate Image: 90-Degree Clockwise Transformation

The "Rotate Image" problem involves rotating a 2D matrix (or image) by 90 degrees clockwise in place.

Problem Statement

Given an n x n matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in place, which means you have to modify the input 2D matrix directly.

Example

• Input: Matrix

[
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

• Output (after rotation):

[
  [7, 4, 1],
  [8, 5, 2],
  [9, 6, 3]
]

Solution Approach (typescript)

function rotate(matrix: number[][]): void {
  const n = matrix.length;

  // Transpose the matrix
  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }

  // Reverse each row
  for (let i = 0; i < n; i++) {
    matrix[i].reverse();
  }
}

Breaking Down the Solution

• Transpose the Matrix: Swap elements across the diagonal to transpose the matrix, turning rows into columns.
• Reverse Each Row: Reverse the elements in each row to achieve the 90-degree clockwise rotation.

Solution Approach (go)

package main

import (
	"fmt"
)

func rotate(matrix [][]int) {
    n := len(matrix)
    // Transpose the matrix
    for i := 0; i < n; i++ {
        for j := i; j < n; j++ {
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        }
    }

    // Reverse each row
    for i := 0; i < n; i++ {
        for j := 0; j < n/2; j++ {
            matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]
        }
    }
}

func main() {
    matrix := [][]int{
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9},
    }

    rotate(matrix)
    fmt.Println("Rotated Matrix:")
    for _, row := range matrix {
        fmt.Println(row)
    }
}

In this Go program:

• The rotate function first transposes the matrix by swapping elements across its diagonal.
• Then, it reverses each row of the matrix. This combination of transposition and reversal results in a 90-degree clockwise rotation.
• The main function demonstrates the usage of the rotate function with a sample matrix.

Solution Approach (cpp)

#include <iostream>
#include <vector>

void rotate(std::vector<std::vector<int>>& matrix) {
    int n = matrix.size();

    // Transpose the matrix
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            std::swap(matrix[i][j], matrix[j][i]);
        }
    }

    // Reverse each row
    for (int i = 0; i < n; ++i) {
        std::reverse(matrix[i].begin(), matrix[i].end());
    }
}

int main() {
    std::vector<std::vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    rotate(matrix);

    // Output the rotated matrix
    for (const auto& row : matrix) {
        for (int val : row) {
            std::cout << val << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

In this solution:

• The function rotate takes a reference to a 2D vector (representing the matrix) and modifies it in place.
• First, the matrix is transposed by swapping elements across the diagonal.
• Then, each row of the matrix is reversed. This combination of transposing and reversing the rows results in a 90-degree clockwise rotation.
• The main function demonstrates the usage of the rotate function with a sample matrix and prints the rotated matrix.

Conclusion

The Rotate Image problem is a classic exercise in matrix manipulation, demonstrating in-place transformations. It's a practical scenario in image processing and graphical applications, testing one's understanding of array operations and geometry.