[Ninja Algorithm] Transform from photo rotation to matrix: Exploring image rotation problem

From photo rotation to matrix transformation: Exploring image rotation problem

The rotation in life

In this era of selfies, we often need to adjust the direction of our photos. Sometimes the photos taken are crooked and need to be rotated 90 degrees; sometimes you want to change the angle to see the effect and rotate the photos back and forth. This rotation operation not only exists in our daily lives, but is also a basic and important operation in the fields of computer graphics, image processing, etc.

Problem description

LeetCode Question 48 "Rotating Images" requires us to: Given a n × n two-dimensional matrix matrix representing an image, rotate the image clockwise by 90 degrees. It is required that the image must be rotated in place, that is, you need to directly modify the input 2D matrix.

For example:

Input: matrix = [[1,2,3],
                 [4,5,6],
                 [7,8,9]]
 Output: [[7,4,1],
        [8,5,2],
        [9,6,3]]

Just like we rotate photos in our mobile album, each pixel needs to be moved to a new location, but we need to ensure that we do not use additional storage space!

The most intuitive solution: auxiliary array

The simplest idea is like we copy a photo and rearrange pixels on new paper. Although this method uses extra space and does not meet the question requirements, it helps us understand the nature of rotation.

Implementation of auxiliary arrays

public void rotate(int[][] matrix) {
     int n = ;
     // Create a new n×n array
     int[][] temp = new int[n][n];
    
     //Save the result after rotating the original matrix by 90 degrees into a temporary array
     for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
             // Key conversion: The element in the i-th column j-th column is rotated to become the j-th column (n-1-i) column after rotation
             temp[j][n-1-i] = matrix[i][j];
         }
     }
    
     // Copy the result back to the original matrix
     for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
             matrix[i][j] = temp[i][j];
         }
     }
 }

Optimization solution: Rotate in place

After careful observation, we found that 90-degree rotation can be completed in two simple steps: first flip along the diagonal line, and then along the vertical midline. Just like origami, you can achieve the effect of rotation by folding twice!

The principle of rotation in place

Imagine you are playing with the Rubik's Cube:

Step 1: Flip along the main diagonal (the upper left to the lower right diagonal)
- [i,j] becomes [j,i]
Step 2: Flip along the vertical midline
- [i,j] becomes [i,n-1-j]

Sample run

Use a 3×3 matrix to illustrate:

Original matrix: Diagonal flip: Vertical midline flip:
 1 2 3 1 4 7 7 4 1
 4 5 6 → 2 5 8 → 8 5 2
 7 8 9 3 6 9 9 6 3

 Step 1: Diagonal flip
 - (1,2) and (2,1) exchange
 - (1,3) and (3,1) exchange
 - (2,3) and (3,2) exchange

 Step 2: Flip the vertical midline
 - Column 1 and 3 exchange
 - Column 2 remains unchanged

Java code implementation

public void rotate(int[][] matrix) {
     int n = ;
    
     // Step 1: Flip along the main diagonal
     for (int i = 0; i < n; i++) {
         for (int j = i; j < n; j++) {
             // Swap matrix[i][j] and matrix[j][i]
             int temp = matrix[i][j];
             matrix[i][j] = matrix[j][i];
             matrix[j][i] = temp;
         }
     }
    
     // Step 2: Flip along the vertical midline
     for (int i = 0; i < n; i++) {
         for (int j = 0; j < n/2; j++) {
             // Swap matrix[i][j] and matrix[i][n-1-j]
             int temp = matrix[i][j];
             matrix[i][j] = matrix[i][n-1-j];
             matrix[i][n-1-j] = temp;
         }
     }
 }

Solution comparison

Let's compare these two methods:

Auxiliary array method:

Time complexity: O(n²)
Space complexity: O(n²)
Advantages: Intuitive and easy to implement
Disadvantages: Additional space is required, which does not meet the requirements of rotating in place

In-situ rotation method:

Time complexity: O(n²)
Space complexity: O(1)
Advantages: No extra space is required, perfectly meeting the requirements of the question
Disadvantages: Need to understand the mathematical principles of matrix transformation

Summary of practical skills

Key points to solve the matrix rotation problem:

Observe the correspondence between elements before and after rotation
Find sub-operations that can be decomposed (such as flip)
Correctly handle boundary situations
Be careful not to repeatedly swap elements

summary

Through the question of rotating images, we learned how to complete matrix rotation through clever mathematical transformations. This way of thinking can not only solve algorithm problems, but is widely used in fields such as image processing and computer graphics. Remember, when encountering problems that require transformation matrix, you can consider decomposing complex transformations into simple operation combinations, which can often lead to a more elegant solution!

Author: Ninja Algorithm
Official account: Ninja Algorithm

I have prepared a list of questions to practice and detailed questions for these questions, covering most common interview questions. I can say responsibly that as long as you truly master these questions, 80% of the algorithm interviews will encounter similar questions. Reply to the official account [Question List] to obtain ~

[Ninja Algorithm] Transform from photo rotation to matrix: Exploring image rotation problem | LeetCode 48 Rotate image