Leetcode: Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

Understand the question:

The question asks for rotating an image by 90 degrees. The question has two requirements:

a. Rotate by 90 degrees in clockwise.

b. Transform in-place.

To understand the problem correctly, we can give several examples to illustrate the question.

For array [1], its transformed array is still 1

For array 1    2

                3   4 , 

the transformed array is     3     1  

                                              4      2

For array 1  2  3

                 4  5  6

                 7  8  9

the transformed array is  7  4  1

                                           8  5  2

                                           9  6  3

So it is not very difficult to see that the transformed array is actually putting first row of the original array into last column of the transformed array, and so on. 

Out-of-place Solution:

Out-of-place solution is very easy. Just crate a buffer to store the transformed array and copy back into the original array after the transformation. 

Code (Java):

public class Solution {
    public void rotate(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return;
        // n * n matrix
        int n = matrix.length;
        
        // Temporary buffter to store rotated image
        int [][] temp = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                temp[j][n - i - 1] = matrix[i][j];
            }
        }
        
        // copy back the results
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = temp[i][j];
            }
        }
    }
}

In-place Solution:
An in-place method is to first transpose the array, then swap the elements in each row.
For example, for array
 1  2  3
 4  5  6
 7  8  9
The transposed array is:
1  4  7
2  5  8
3  6  9
Then swap elements in each row
7  4  1
8  5  2
9  6  3

Code (Java):

public class Solution {
    public void rotate(int[][] matrix) {
        if (matrix == null || matrix.length < 2) return;
        
        // length of the matrix
        int n = matrix.length;
        
        // transpose the matrix
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        
        // swap elements for each row
        int mid = n / 2;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < mid; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[i][n - j - 1];
                matrix[i][n - j - 1] = tmp;
            }
        }
    }
}

Discussion:
The time complexity is O(n^2), which is the best we can do for this algorithm. The space complexity is O(1). Note the matrix transpose algorithm, the inner loop index j starting from i + 1. That is because we have already swapped the element before i. If j starts from 0, it will swap the elements back again.

Another in-place solution:
Check cc150 1.6

Code (Java):

public class Solution {
    public void rotate(int[][] matrix) {
        // check if matrix is null or empty or length equals to 1
        if (matrix == null || matrix.length < 2) return;
        
        int n = matrix.length;
        
        for (int layer = 0; layer < n/2; layer++) {
            int first = layer;
            int last = n - layer - 1;
            
            for (int i = first; i < last; i++) {
                int offset = i - first;
                int top = matrix[first][i];
                
                // left -> top
                matrix[first][i] = matrix[last - offset][first];
                
                // bottom -> left
                matrix[last - offset][first] = matrix[last][last - offset];
                
                // right -> bottom
                matrix[last][last - offset] = matrix[i][last];
                
                // top - > right;
                matrix[i][last] = top;
            }
        }
    }
} 

Summary:
In this post, we learned how to rotate an array in place. The third method is very tricky. Make sure to understand the details, especially for how to calculate the indices.