048_rotate_image.md

48. Rotate Image

---

https://leetcode.com/problems/rotate-image/description/

Topic

• Array
• Math
• Matrix

---

Brain Strom

Induction

let's see how the element move:

Element	From (row, col)	To (row, col)
1	(0, 0)	(0, 2)
2	(0, 1)	(1, 2)
3	(0, 2)	(2, 2)
4	(1, 0)	(0, 1)
5	(1, 1)	(1, 1)
6	(1, 2)	(2, 1)
7	(3, 0)	(0, 0)
8	(3, 1)	(1, 0)
9	(3, 2)	(2, 0)

As the above we saw, we can infer the movement regulation formula.

n = Square side length (in this case n = 3)

Matrix(row, col) -- Rotate Transfer -> Matrix(col, n-1-row) 

If we ignore the rule: DO NOT allocate another 2D matrix and do the rotation. what we can do?

define a new 2D array, and iterate through the input 2D array, put element into new 2D array by transfer formula.

Like:

• do loop
• find original element 1 in position [0, 0]
• calculate new position lelement 1 to [0, 2]
• put 1 into new2DArr[0, 2]
• next loop

But when it come with in place rule, we can't do it like this. So what we can do?

Flip horizontally & Flip diagonally.

What if we do do this 2D array with Flip horizontally ?

let's check it out:

---------
1 | 2 | 3
---------
4 | 5 | 6
---------
7 | 8 | 9

> Flip horizontally:

---------
7 | 8 | 9
---------
4 | 5 | 6
---------
1 | 2 | 3

The flip horizontally formula is:

Matrix (row, col) -> Matrx (n-1-row, col)

What if we do do this 2D array with Flip diagonally ?

---------
1 | 2 | 3
---------
4 | 5 | 6
---------
7 | 8 | 9

Flip diagonally:

---------
1 | 4 | 7
---------
2 | 5 | 8
---------
3 | 6 | 9

The filp diagonally formula is:

Matrix (row, col) -> Matrx (col, row)

Now we zoom out, let check those three formula:

# 90 degree rotate:

Matrix(col, n-1-row) 

---------------------------------

# Flip horizontally:

Matrx(n-1-row, col)

---------------------------------

# Flip diagonally

Matrx(col, row)

---------------------------------

90 degree rotate is actually equals to Flip horizontally + Flip diagonally !

Matrix(col, n-1-row) = Matrx(n-1-row, col) + Matrx(col, row)

The solution is do 1 time flip hirizontally then do 1 time flip diagonally too.

---

impl Solution {
    pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
        let side_length = matrix.len() as usize;

        // 1. do flip horizontally.
        Self::flip_horizontally(matrix, side_length);
        // 2. do flip diagonally.
        Self::flip_diagonally(matrix, side_length);
    }

    // How to flip horizontally?
    // Swap Matrix(row, col) to Matrix(n-1-row, col)
    fn flip_horizontally(matrix: &mut Vec<Vec<i32>>, side_length: usize) {
        for i in 0..side_length / 2 {
            for j in 0..side_length {
                let temp = matrix[i as usize][j as usize];
                matrix[i as usize][j as usize] = matrix[side_length - 1 - i as usize][j as usize];
                matrix[side_length - 1 - i as usize][j as usize] = temp;
            }
        }
    }

    // How to flip diagonally?
    // Swap Matrix(row, col) to Matrix(col, row)
    fn flip_diagonally(matrix: &mut Vec<Vec<i32>>, side_length: usize) {
        for i in 0..side_length {
            for j in i..side_length {
                let temp = matrix[i as usize][j as usize];
                matrix[i as usize][j as usize] = matrix[j as usize][i as usize];
                matrix[j as usize][i as usize] = temp;
            }
        }

    }
}