0 ms, O(1) space Java solution


  • 0
    S

    Let's use matrix[a][b] -> matrix[a'][b'] to represent: the value of matrix[a][b] will be in matrix[a'][b'] after rotation.

    So start from any cell, we have:
    matrix[x][y] -> matrix[y, n - 1 - x] -> matrix[n - 1 - x][n - 1 - y] -> matrix[n - 1 - y][x] -> matrix[x][y].

    It's like shifting the values amount the four cells. So, we can solve 4 cells together. Here is an example 5 * 5 matrix:

    11111
    12221
    12321
    12221
    11111
    

    Starting from the first row, we do the "4-cell shifting" starting from each of the cells except for the last (which is not necessary), all the outer bound cells (marked with '1') in the matrix have the correct values. You can understand this by drawing a 4*4 matrix.

    We then go to the second row. This time, we don't need to care the first and last cell, because their values are already correct. They belongs to the outer bound of the matrix. After we finish the second row (three cells marked with '2'), all cells in the "second out-most" bound are done.

    In the third row, we skip 2 cells from both left and right in the row, because their values are already updated. The number of cells to skip is gap in the code. Now, there are only one cell to deal with (marked with '3'). We don't need to do anything now.

    // skip first and last "gap" number of cells.
    public void rotate(int[][] matrix) {
    	int n = matrix.length;
    	for (int gap = 0; gap < n / 2; gap++) {
    		for (int y = gap; y < n - gap - 1; y++) {
    			int temp = matrix[gap][y];
    			matrix[gap][y] = matrix[n - y - 1][gap];
    			matrix[n - y - 1][gap] = matrix[n - gap - 1][n - y - 1];
    			matrix[n - gap - 1][n - y - 1] = matrix[y][n - gap - 1];
    			matrix[y][n - gap - 1] = temp;
    		}
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.