LeetCode - Algorithms - 48. Rotate Image

Done by myself. Aha following step with 867. Transpose Matrix. After I solved it, I found this In-place rotate matrix by 90 degrees in clock-wise direction on web. Interesting. It is likely to be an elegant solution to this problem. “There is no algorithm for creativity.”, as Andy Hargreaves had ever said.

Problem

48. Rotate Image

Java

1

transpose and then swap columns symmetrically

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void rotate(int[][] matrix) {
        int N = matrix.length;
        int tmp;
        for(int i=0; i<N; i++) {
            for(int j=0; j<i; j++) {
                tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        for(int i=0; i<N; i++) {
            for(int j=0; j<N/2; j++) {
                tmp = matrix[i][j];
                matrix[i][j] = matrix[i][N-1-j];
                matrix[i][N-1-j] = tmp;
            }
        }        
    }
}

Submission Detail

  • 21 / 21 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Rotate Image.
  • Memory Usage: 39.4 MB, less than 5.77% of Java online submissions for Rotate Image.

2

solution of www.geeksforgeeks.org

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public void rotate(int[][] matrix) {
        int N = matrix.length;
        int tmp;
        for(int i=0; i<N/2; i++) {
            for(int j=i; j<N-i-1; j++) {
                tmp = matrix[i][j];
                matrix[i][j] = matrix[N-1-j][i];
                matrix[N-1-j][i] = matrix[N-1-i][N-1-j];
                matrix[N-1-i][N-1-j] = matrix[j][N-1-i];
                matrix[j][N-1-i] = tmp;
            }
        }        
    }
}

Submission Detail

  • 21 / 21 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Rotate Image.
  • Memory Usage: 39.4 MB, less than 5.77% of Java online submissions for Rotate Image.

non in-place method

matrix rotate

1
2
3
4
5
6
7
8
9
10
public int[][] rotate_math_stackexchange(int[][] matrix) {
    int N = matrix.length;
    int[][] R = new int[N][N];
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            R[i][j] = matrix[N-1-j][i];
        }
    }
    return R;
}

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function(matrix) {
    var n = matrix.length;
    var tmp;
    for(var i=0; i<n; i++) {
        for(var j=0; j<i; j++) {
            tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }
    for(var i=0; i<n; i++) {
        for(var j=0; j<n/2; j++) {
            tmp = matrix[i][j];
            matrix[i][j] = matrix[i][n-1-j];
            matrix[i][n-1-j] = tmp;
        }
    }    
};

Submission Detail

  • 21 / 21 test cases passed.
  • Runtime: 56 ms, faster than 57.20% of JavaScript online submissions for Rotate Image.
  • Memory Usage: 33.4 MB, less than 100.00% of JavaScript online submissions for Rotate Image.