Rotate Matrix

Question (LC.48)

Given a mxn matrix, can you rotate it clockwise and counter-clockwise? Can you do it in place?

Analysis

There are two approaches. One way to do it layer by layer. The second approach requires some linear algebra knowledge. Here we'll discuss the second approach - transposing and flipping the matrix.

Transpose

Transpose the matrix first n x m result[x][y] = matrix[y][x] m x n

private int[][] transpose(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    int[][] result = new int[n][m];

    for (int y = 0; y < m; y++) {
        for (int x = 0; x < n; x++) {
            result[x][y] = matrix[y][x];
        }
    }

    return result;
}

Vertical/Horizontal Flip

If rotate clockwise, flip horizontally.

If rotate counterclockwise, flip vertically.

private void horizontalFlip(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;

    for (int y = 0; y < m; y++) {
        for (int x = 0; x < n/2; x++) {
            int temp = matrix[y][x];
            matrix[y][x] = matrix[y][n - 1 - x];
            matrix[y][n - 1- x] = temp;
        }
    }
}

private void verticalFlip(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;

    for (int x = 0; x < n; x++) {
        for (int y = 0; y < m/2; y++) {
            int temp = matrix[y][x];
            matrix[y][x] = matrix[m - 1 - y][x];
            matrix[m - 1 - y][x] = temp;
        }
    }
}

Rotate Matrix

public int[][] rotateMatrix(int[][] matrix, int flag) {
    if (matrix == null || matrix.length == 0)
        return matrix;
    if (matrix[0] == null || matrix[0].length == 0)
        return matrix;
    int[][] result;
    result = transpose(matrix);

    if (flag == 1) // rotate clockwise
        horizontalFlip(result);
    else // rotate counterclockwise
        verticalFlip(result);
    return result;
}

Note

Rotation in-place has very limited options in terms of operation. You pretty much have to figure out a way that only uses swapping elements and holding a temp variable. Swapping horizontally, vertically, diagonally, multiple times (with different substrings), etc.