Question

Formatted question description: https://leetcode.ca/all/48.html

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Example 1:

Given input matrix =
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Example 2:

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

rotate the input matrix in-place such that it becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]


Follow up:
Could you do this in-place?

@tag-array

Algorithm

Use a simple example to analyze:

1 2 3       7 4 1 

4 5 6  -->   8 5 2  

7 8 9        9 6 3

There are many ways to flip 90 degrees, one or more steps can be solved, first look at a direct method, this method is to cover the previous numbers in a clockwise order, starting from the four top corners, and then To traverse in the middle, the coordinates covered each time are the same, as follows:

(i, j) <- (n-1-j, i) <- (n-1-i, n-1-j) <- (j, n-1-i)

This is actually a cyclic process. The first position covers the fourth position, where the value range of i is [0, n/2), and the value range of j is [i, n-1-i), As for why i and j are in this value range, why i don’t need to traverse [n/2, n). If you carefully observe the relationship between these positions, it is not difficult to find that the range of column j is actually [i, n-1 -i) Turn 90 degrees clockwise, which is exactly the position of [n/2, n) in row i. This method changes four numbers each time through the loop

Note

I missed a key concept, I DO NOT have to rotate all numbers on one edge from start to end

1. for corner positions of each layer, rotate first is also changing end of that layer row
2. for numbers not corner, rotate them


eg:
	1 2
	3 4

	one rotate is enough, since except corner position, no other positions


eg:
	1   2   3   4   5
	6   7   8   9   10
	11  12  13  14  15
	16  17  18  19  20
	21  22  23  24  25

	like in row "1,2,3,4,5", rotate 1 will also change 5
	so, for each edge, rotate to the penultimate one, that is, only rotate "1,2,3,4" is enough, and 5 will be processed in the next operation

Code

Java

  • 
    
    public class Rotate_Image {
    
    	public class Solution {
    	    /*  eg:
    
    	        1   2   3   4   5
    	        6   7   8   9   10
    	        11  12  13  14  15
    	        16  17  18  19  20
    	        21  22  23  24  25
    	    */
    
    	    public void rotate(int[][] m) { // m for matrix
    
    	        if (m == null || m.length == 0) {
    	            return;
    	        }
    
    	        // for each circle, start position is (i,i), length is rectangle size
    	        // eg. above: (0,0), length=5; (1,1), length=3
    	        int i = 0;
    	        int length = m.length;
    
    	        while (i < m.length / 2) {
    
    	            int count = 0;
    	            while (count < length - 1) { // @note: extra attention here "-1".
    	            // while (count < length) {
    
    	                int tmp = m[i][i + count];
    
    	                // i+length-1: last index of this rectangle
    	                // i+length-1 - count: index from backward
    	                m[i][i + count] = m[i + length - 1 - count][i];
    	                m[i + length - 1 - count][i] = m[i + length - 1][i + length - 1 - count];
    	                m[i + length - 1][i + length - 1 - count] = m[i + count][i + length - 1];
    	                m[i + count][i + length - 1] = tmp;
    
    	                count++;
    	            }
    
    	            length -= 2; // @note: shrink each edge length by 2
    	            i++; // start point moving along diagonal
    	        }
    	    }
    	}
    
    	// An Inplace function to rotate a N x N matrix by 90 degrees in anti-clockwise direction
    	static void rotateMatrix_anticlock(int N, int mat[][])
    	{
    		// Consider all squares one by one
    		for (int x = 0; x < N / 2; x++) {
    			// Consider elements in group of 4 in
    			// current square
    			for (int y = x; y < N-x-1; y++) {
    				// store current cell in temp variable
    				int temp = mat[x][y];
    
    				// move values from right to top
    				mat[x][y] = mat[y][N-1-x];
    
    				// move values from bottom to right
    				mat[y][N-1-x] = mat[N-1-x][N-1-y];
    
    				// move values from left to bottom
    				mat[N-1-x][N-1-y] = mat[N-1-y][x];
    
    				// assign temp to left
    				mat[N-1-y][x] = temp;
    			}
    		}
    	}
    
    	static void rotateMatrix_clockwise(int N, int mat[][])
    	{
    		// Consider all squares one by one
    		for (int x = 0; x < N / 2; x++) {
    			// Consider elements in group of 4 in
    			// current square
    			for (int y = x; y < N-x-1; y++) {
    				// store current cell in temp variable
    				int temp = mat[x][y];
    
    				// move values from right to top
    				mat[x][y] = mat[y][N-1-x];
    
    				// move values from bottom to right
    				mat[y][N-1-x] = mat[N-1-x][N-1-y];
    
    				// move values from left to bottom
    				mat[N-1-x][N-1-y] = mat[N-1-y][x];
    
    				// assign temp to left
    				mat[N-1-y][x] = temp;
    			}
    		}
    	}
    }
    
  • // OJ: https://leetcode.com/problems/rotate-image/
    // Time: O(N^2)
    // Space: O(1)
    class Solution {
    public:
        void rotate(vector<vector<int>>& A) {
            int N = A.size();
            for (int i = 0; i < N / 2; ++i) {
                for (int j = i; j < N - i - 1; ++j) {
                    int tmp = A[i][j];
                    A[i][j] = A[N - j - 1][i];
                    A[N - j - 1][i] = A[N - i - 1][N - j - 1];
                    A[N - i - 1][N - j - 1] = A[j][N - i - 1];
                    A[j][N - i - 1] = tmp;
                }
            }
        }
    };
    
  • class Solution(object):
      def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        if len(matrix) == 0:
          return
        h = len(matrix)
        w = len(matrix[0])
        for i in range(0, h):
          for j in range(0, w / 2):
            matrix[i][j], matrix[i][w - j - 1] = matrix[i][w - j - 1], matrix[i][j]
    
        for i in range(0, h):
          for j in range(0, w - 1 - i):
            matrix[i][j], matrix[w - 1 - j][h - 1 - i] = matrix[w - 1 - j][h - 1 - i], matrix[i][j]
    
    

another way: transpose + reflect

reference https://leetcode.com/problems/rotate-image/solution/

original

[
	[1,2,3],
	[4,5,6],
	[7,8,9]
]

diagonal as reverse base line

[
	[1,4,7],
	[2,5,8],
	[3,6,9]
]

every row, to reverse from left to right

[
	[7,4,1],
	[8,5,2],
	[9,6,3]
]

java implementation

  • class Solution_diagonal {
    	public void rotate(int[][] matrix) {
    		transpose(matrix);
    		reflect(matrix);
    	}
    
    	public void transpose(int[][] matrix) {
    		int n = matrix.length;
    		for (int i = 0; i < n; i++) {
    			for (int j = i; j < n; j++) {
    				int tmp = matrix[j][i];
    				matrix[j][i] = matrix[i][j];
    				matrix[i][j] = tmp;
    			}
    		}
    	}
    
    	public void reflect(int[][] matrix) {
    		int n = matrix.length;
    		for (int i = 0; i < n; i++) {
    			for (int j = 0; j < n / 2; j++) {
    				int tmp = matrix[i][j];
    				matrix[i][j] = matrix[i][n - j - 1];
    				matrix[i][n - j - 1] = tmp;
    			}
    		}
    	}
    }
    
  • // OJ: https://leetcode.com/problems/rotate-image/
    // Time: O(N^2)
    // Space: O(1)
    class Solution {
    public:
        void rotate(vector<vector<int>>& A) {
            int N = A.size();
            for (int i = 0; i < N / 2; ++i) {
                for (int j = i; j < N - i - 1; ++j) {
                    int tmp = A[i][j];
                    A[i][j] = A[N - j - 1][i];
                    A[N - j - 1][i] = A[N - i - 1][N - j - 1];
                    A[N - i - 1][N - j - 1] = A[j][N - i - 1];
                    A[j][N - i - 1] = tmp;
                }
            }
        }
    };
    
  • class Solution(object):
      def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        if len(matrix) == 0:
          return
        h = len(matrix)
        w = len(matrix[0])
        for i in range(0, h):
          for j in range(0, w / 2):
            matrix[i][j], matrix[i][w - j - 1] = matrix[i][w - j - 1], matrix[i][j]
    
        for i in range(0, h):
          for j in range(0, w - 1 - i):
            matrix[i][j], matrix[w - 1 - j][h - 1 - i] = matrix[w - 1 - j][h - 1 - i], matrix[i][j]
    
    

All Problems

All Solutions