# 48. Rotate Image

Description:

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

Algorithm:

 4 4 4 4 4 4 -> 2 -> 4 4 2 0 2 4 4 <- 2 <- 4 4 4 4 4 4
• n is odd (in our example,  n = 5)
• the central blue one (n/2, n/2) = (2, 2) doesn’t move
• the k-th outer ring moves clockwise for 2 * k units, the k-th ring contains 8 * k units
• How to move?
• row index: i, col index j
• start from i = n/2 – k, j= n/2 – k and go for the whole ring
• move right:   if (i < m + k && j == m – k)  i = i + 1, j = j
• move down: if (i == m + k &&  j < m + k)  j = j + 1, i = i
• move left:     if (i > m – k && j == m + k)  i = i – 1, j = j
• move up:      if (i == m – k && j > m – k)  j = j – 1, i = i
• tmp = matrix[newIndex] AND matrix[newIndex] = matrix[oldIndex]
• oldIndex = newIndex
• n is even
• there is no central fixed uint!
• the k-th outer ring moves clockwise for 2 * k – 1 units, the k-th ring contains 8 * (k – 1) +4 units
• How to move?
• row index: i, col index j
• start from i = n/2 – k, j= n/2 – k and go for the whole ring
• move right:   if (i < m + k – 1 && j == m – k)  i = i + 1, j = j
• move down: if (i == m + k – 1 &&  j < m + k – 1)  j = j + 1, i = i
• move left:     if (i > m – k && j == m + k – 1)  i = i – 1, j = j
• move up:      if (i == m – k && j > m – k)  j = j – 1, i = i
• tmp = matrix[newIndex] AND matrix[newIndex] = matrix[oldIndex]
• oldIndex = newIndex

Code:
``` class Solution { public: void rotate(vector<vector>& matrix) { int m = matrix.size() / 2; if (m < 1) return; if (matrix.size() % 2) { for (int k = 1; k <= m; k++) { for (int l = 0; l < 2 * k; l++) ```

`              ``{ `

`                  int elementNum = 8 * k; int i = m - k; int j = m - k; int tmp = matrix[j][i]; `

```                  while (elementNum > 0) { int i_new = (i < m + k && j == m - k) ? i + 1 : (i > m - k && j == m + k) ? i - 1 : i; int j_new = (j < m + k && i == m + k) ? j + 1 : (j > m - k && i == m - k) ? j - 1 : j; swap(matrix[j_new][i_new], tmp); i = i_new; j = j_new; elementNum--; } } } } else { for (int k = 1; k <= m; k++) { for (int l = 0; l < k * 2 - 1; l++) { ```

`                   int elementNum = 8 * (k - 1) + 4; int i = m - k; int j = m - k; int tmp = matrix[j][i]; `

`    ``             ````while (elementNum > 0) { int i_new = (i < m - 1 + k && j == m - k) ? i + 1 : (i > m - k && j == m - 1 + k) ? i - 1 : i; int j_new = (j < m - 1 + k && i == m - 1 + k) ? j + 1 : (j > m - k && i == m - k) ? j - 1 : j; swap(matrix[j_new][i_new], tmp); i = i_new; j = j_new; elementNum--; } } } } } }; ```

Timing:

Luckily time is good…3ms (fastest)

complexity: O(n)

n is the number of elements.