48. Rotate Image

Description

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.

Constraints

• matrix.length == n

• matrix[i].length == n

• 1 <= n <= 20

• -1000 <= matrix[i][j] <= 1000

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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

Example 3

Input: matrix = [[1]]

Output: [[1]]

Example 4

Input: matrix = [[1, 2], [3, 4]]

Output: [[3, 1], [4, 2]]

Solutions

Solution 1

/**
 * Time complexity : O(N*N)
 * Space complexity : O(1)
 */

class Solution {
    public void rotate(int[][] matrix) {
        if(matrix == null || matrix.length == 0) return;
        
        int row = matrix.length,
            col = matrix.length;
        
        // trnspose of a matrix
        for(int r = 0; r < row; r++) {
            for(int c = r+1; c < col; c++) {
                int tmp = matrix[r][c];
                matrix[r][c] = matrix[c][r];
                matrix[c][r] = tmp;
            }
        }
        
        // swap columns
        for(int c = 0; c < col/2; c++) {
            for(int r = 0; r < row; r++) {
                int tmp = matrix[r][c];
                matrix[r][c] = matrix[r][col-c-1];
                matrix[r][col-c-1] = tmp;
            }
        }
                
    }
}

Solution 2

/**
 * Time complexity : O(N*N)
 * Space complexity : O(1)
 */
 
class Solution {
    public void rotate(int[][] matrix) {
        if(matrix == null || matrix.length <= 1) return;
        
        int n = matrix.length;

        for(int layer = 0; layer < n/2; layer++) {
            for(int i = layer; i < n-layer-1; i++) {
                int tmp = matrix[layer][i];
                matrix[layer][i] = matrix[n-i-1][layer];
                matrix[n-i-1][layer] = matrix[n-layer-1][n-i-1];
                matrix[n-layer-1][n-i-1] = matrix[i][n-layer-1];
                matrix[i][n-layer-1] = tmp;
            }
        }     
    }
}

Follow up