Array Algorithm: Rotate an image

An image representing as a 2D matrix. You can take some time to read the problem:

You are given an n x n 2D 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. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

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

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Example 3:

Input: matrix = [[1]]
Output: [[1]]

Example 4:

Input: matrix = [[1,2],[3,4]]
Output: [[3,1],[4,2]]

Constraints:

matrix.length == n

matrix[i].length == n

1 <= n <= 20

-1000 <= matrix[i][j] <= 1000

Solution

We will try to rotate on the paper to find the rules on how it rotates. It looks like we just pull out 4 elements top, right, bottom, and left then swap its value.
But how do it continuously? We can think of an iterator from 0 to the size of a row, each iteration just increase i variable straightforward, and the size of a row is equal to the size of the column, then we can play around with the i variable and the length of the row to reach all the matrix positions.
But it is not enough, a matrix may have several layers based on its size, imagine a 3x3 Rubik, you rotate the outside layer but not the center cell, and for the 4x4 matrix, you have no center cell, 2 layers will be rotating. So we can come to the rule of the number of layers like layers = matrix length / 2.
Now we play around with layer, size(length), and i (a row iterator) to reach all the matrix positions. Let resolve a subproblem first.

var top = matrix[layer][i];
var right = matrix[i][length - layer];
var bot = matrix[length - layer][length -i];
var left = matrix[length - i][layer];

Look at the positions,

• Top will be fixed the row, only the column moving by i
• Right fixed by the column, only the row moving by i
• Bottom fixed by the row, opposite of the top
• Left fixed by the column, opposite of the right

After pulling out all the four positions, we assign its new position

// top = left
matrix[layer][i] = left;
// right = top
matrix[i][length - layer] = top;
// bot = right
matrix[length - layer][length - i] = right;
// left = bot
matrix[length - i][layer] = bot;

The complete code would be.

public class Solution {
    public void Rotate(int[][] matrix) {
        var layers = matrix.Length / 2;
        var length = matrix.Length - 1;
        
        for(var layer = 0; layer < layers; layer++){
            
            for(var i = layer; i < length - layer; i++){
                var top = matrix[layer][i];
                var right = matrix[i][length - layer];
                var bot = matrix[length - layer][length -i];
                var left = matrix[length - i][layer];
                    
                // top = left
                matrix[layer][i] = left;
                // right = top
                matrix[i][length - layer] = top;
                // bot = right
                matrix[length - layer][length - i] = right;
                // left = bot
                matrix[length - i][layer] = bot;
            }
        }
    }
}

The time complexity: O(n * n) as we reached all the values of matrix

The space complexity is O(1) as we don’t have any extra space.