Rotate Matrix

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees.

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]]

Constraints:

• n == matrix.length == matrix[i].length

• 1 <= n <= 20

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

Solutions

Because we're rotating the matrix by 90 degrees, the easiest way to do this is to implement the rotation in layers. We perform a circular rotation on each layer, moving the top edge to the right edge, the right edge to the bottom edge, the bottom edge to the left edge, and the left edge to the top edge.

How do we perform this four-way edge swap? One option is to copy the top edge to an array, and then move the left to the top, the bottom to the left, and so on. This requires O(N) memory, which is actually unnecessary.

image

public class Solution {
    public void Rotate(int[][] matrix) {
        if (matrix is null || matrix.Length == 0 || matrix.Length != matrix[0].Length)
            return;

        for (int layer = 0; layer < matrix.Length / 2; layer++) //90 degree
        {
            int first = layer;
            int last = matrix.Length - 1 - layer;
            for (int i = first; i < last; i++)
            {
                int offset = i - first;

                int top = matrix[first][i]; // save top
                // 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; // right<-saved top
            }
        }
    }
}

Time complexity: O(n²)

Space complexity: O(1)