48. Rotate Image

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

Constraints:

n == matrix.length == matrix[i].length
1 <= n <= 20
1000 <= matrix[i][j] <= 1000

Solution 1

Explanation

Code (Rust)

#![allow(unused)]
fn main() {
impl Solution {
    pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
        Solution::transpose(matrix);
        Solution::y_reflection(matrix);
    }

    fn transpose(matrix: &mut Vec<Vec<i32>>) {
        let n = matrix.len();
        for i in 0..n {
            for j in (i+1)..n {
		            let temp = matrix[i][j];
		            matrix[i][j] = matrix[j][i];
		            matrix[j][i] = temp;
            }
        }
    }

    fn y_reflection(matrix: &mut Vec<Vec<i32>>) {
        let n = matrix.len();
        for i in 0..n {
            for j in 0..(n/2) {
		            let temp = matrix[i][j];
		            matrix[i][j] = matrix[i][n - 1 - j];
		            matrix[i][n - 1 - j] = temp;
            }
        }
    }
}
}

Solution 2

Explanation

We can rotate elements from exterior to interior by swapping area 1 and 2, swapping area 2 and 3, and area 3 and 4.

Code (Rust)

#![allow(unused)]
fn main() {
impl Solution {
    pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
       let mut i = 0;
       let n = matrix.len();
         
       while i < n / 2 {
           // swap 1 2
           for j in i..=(n-i-2){
               let temp = matrix[i][j];
               matrix[i][j] = matrix[j][n - i - 1];
               matrix[j][n - i - 1] = temp;
           }
           // swap 2 3
           for j in i..=(n-i-2){
               let temp = matrix[i][j];
               matrix[i][j] = matrix[n - i - 1][n - 1 - j];
               matrix[n - i - 1][n - 1 - j] = temp;
           }
           // swap 3 4
           for j in i..=(n-i-2){
               let temp = matrix[i][j];
               matrix[i][j] = matrix[n - 1 - j][i];
               matrix[n - 1 - j][i] = temp;
           }
           i+=1;
       }
	}
}
}

Further Discussion

This problem though seems very easy, is very important in daily life. If we have to allocate another 2d array for rotation, we have to spend more memory on photo editing.

Leetbook