1
\$\begingroup\$

Please suggest improvements and a possible better way of doing it in place.

public static void main(String[] args) {
    int[][] mat = { { 1, 2 }, { 3, 4 } };
    rotate(mat);
}

public static void rotate(int[][] matrix) {
    if (matrix == null) {
        return;
    }
    int n = matrix.length - 1;
    int temp = 0;
    int[][] mat2 = new int[n + 1][n + 1];
    mat2 = matrix;
    for (int row = 0; row <= n; row++) {
        for (int col = 0; col <= n; col++) {
            // mat2[n-col][row] = matrix[row][col];
            temp = matrix[col][n - row];
            matrix[col][n - row] = matrix[row][col];
            matrix[row][col] = temp;
        }
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            matrix[i][j] = mat2[i][j];
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I do not understand why you don't directly assign to mat2 - the whole tmp switching would be unneccesary. I really have a problem following your idea through due to this. Does it actually do what you expect? \$\endgroup\$ – bdecaf Feb 18 '16 at 13:14
  • 1
    \$\begingroup\$ The given code doesn't work. It doesn't rotate the matrix by 90 degrees. \$\endgroup\$ – Tunaki Feb 18 '16 at 13:29
4
\$\begingroup\$

Yes there is a better way to do it. It makes the computation really simple and elegant.

If you take the transpose of the matrix and then rotate the matrix row-wise along the mid row, you can get the same result as rotating the matrix by 90 degrees counter clock-wise.

For example:

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

Step 1: take its transpose:

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

Step 2: rotate the matrix across mid row:

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

This is exactly what you get when you rotate the matrix by 90 degrees left.

Here is the code:

public static void rotateMatrix(int[][] matrix){
    if(matrix == null)
        return;
    if(matrix.length != matrix[0].length)//INVALID INPUT
        return;
    getTranspose(matrix);
    rorateAlongMidRow(matrix);      
}

private static void getTranspose(int[][] matrix) {
    for(int i = 0; i < matrix.length; i++){
        for(int j = i+1; j < matrix.length ; j++){
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}

private static void rorateAlongMidRow(int[][] matrix) {
    int len = matrix.length ;
    for(int i = 0; i < len/2; i++){
        for(int j = 0;j < len; j++){
            int temp = matrix[i][j];
            matrix[i][j] = matrix[len-1 -i][j];
            matrix[len -1 -i][j] = temp;
        }
    }
}

Edit: As suggested in the comment, for making it rotate clock-wise, just change the function getTranspose() to rotateAlongDiagonal() in rotateMatrix() function.

private static void rotateAlongDiagonal(int[][] matrix) {
    int len = matrix.length;
    for(int i = 0; i < len; i++){
        for(int j = 0; j < len - 1 - i ; j++){
            int temp = matrix[i][j];
            matrix[i][j] = matrix[len -1 - j][len-1-i];
            matrix[len -1 - j][len-1-i] = temp;
        }
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ didn't you rotate counter clock wise? shouldn't it it something like [[7,4,1], [8,5,2], [9,6,3]] \$\endgroup\$ – Armin Feb 19 '16 at 23:34
  • \$\begingroup\$ Thanks @Armin. Yes that's correct. For making it rotate clockwise, rotate the matrix along other diagonal rather than taking a transpose. \$\endgroup\$ – maxomax Feb 20 '16 at 0:13
  • 1
    \$\begingroup\$ then, shouldn't you edit your answer, so it fits the given task? \$\endgroup\$ – Armin Feb 20 '16 at 0:57
  • 1
    \$\begingroup\$ By "rotate the matrix row-wise along the mid row", I think you mean "reflect the matrix about the middle row". \$\endgroup\$ – 200_success Feb 29 '16 at 6:44
3
\$\begingroup\$

Here's a single-pass way to do it. Check the rotateClockwise method. The rest is accessory, but might be worth checking too. In the spirit of object-oriented code reviewing, I made a class around your matrix. Further optimize for code length or performance as needed.

The idea is to consider the matrix as a series of concentric squares (or rings), starting with the outermost one. For each square, starting top left, save the value in temp. Go bottom left, store that value top left. Move the bottom right value bottom left. Etc. It's basically a 4-way swap. Do this for the square's corners, then the values beside them. I move clockwise on the squares between each set of 4 values to swap, but move the values themselves counter-clockwise (not that it matters, but it may help you understand the code). It's admittedly way more confusing than transpose + rotate rows/cols, but it's still another way to do it.

Just to help grasp the matrix indices...

  • s is the concentric square index. It therefore can be used as matrix index offset when moving towards inner squares (so it's 0 when doing the outermost square and has no effect then).
  • -1 are applied to len, the matrix order (matrix length). Needed to avoid out of bounds index issues.
  • i is used to iterate on square sides. Goes from corner to next to last item.

The class, with test main:

/** Integer square matrix class. Clockwise rotation and pretty printing. */
public class IntSquareMatrix {

    private int[][] mat;

    /** Creates a matrix from given array. */
    public IntSquareMatrix(int[][] initialState) {
        mat = initialState;
    }

    /** Creates a matrix with continuous values for tests. */
    public IntSquareMatrix(int order) {
        mat = new int[order][order];
        for (int i = 0; i < order; i++)
            for (int j = 0; j < order; j++)
                mat[i][j] = i * order + j;
    }

    public void rotateClockwise() {
        int temp;
        final int len = mat.length;
        // For each concentric square around the middle of the matrix to rotate...
        // This value will be used as (m, n) offset when moving in.
        // Integer division by 2 will skip center if odd length.
        for (int s = 0; s < len / 2; s++)
            // for the length of this ring
            for (int i = 0; i < len - 2 * s - 1; i++) {
                temp = mat[s][s + i];
                mat[s][s + i] = mat[len - s - i - 1][s];
                mat[len - s - i - 1][s] = mat[len - s - 1][len - s - i - 1];
                mat[len - s - 1][len - s - i - 1] = mat[s + i][len - s - 1];
                mat[s + i][len - s - 1] = temp;
            }
    }

    /**
     * Calculates the maximum width of matrix values for nicer printing.
     * @return cell format String
     */
    private String cellFormat() {
        int absMax = 0;
        for (int[] row : mat)
            for (int val : row)
                if (Math.abs(val) > absMax)
                    absMax = Math.abs(val);
        int cellWidth = (int) Math.log10(absMax) + 2; // account for negatives
        return "% " + cellWidth + "d "; // pad left with spaces
    }

    @Override
    public String toString() {
        String cellFormat = cellFormat();
        StringBuilder sb = new StringBuilder();
        for (int[] row : mat) {
            sb.append("[ ");
            for (int val : row)
                sb.append(String.format(cellFormat, val));
            sb.append("]\n");
        }
        return sb.toString();
    }

    // doesn't belong here, just a demo
    public static void main(String[] args) {
        for (int order = 2; order <= 5; order++) {
            IntSquareMatrix mat = new IntSquareMatrix(order);
            System.out.println("Original:\n" + mat);
            mat.rotateClockwise();
            System.out.println("Rotated:\n" + mat);
        }
    }

}

Its output:

Original:
[  0  1 ]
[  2  3 ]

Rotated:
[  2  0 ]
[  3  1 ]

Original:
[  0  1  2 ]
[  3  4  5 ]
[  6  7  8 ]

Rotated:
[  6  3  0 ]
[  7  4  1 ]
[  8  5  2 ]

Original:
[   0   1   2   3 ]
[   4   5   6   7 ]
[   8   9  10  11 ]
[  12  13  14  15 ]

Rotated:
[  12   8   4   0 ]
[  13   9   5   1 ]
[  14  10   6   2 ]
[  15  11   7   3 ]

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

Rotated:
[  20  15  10   5   0 ]
[  21  16  11   6   1 ]
[  22  17  12   7   2 ]
[  23  18  13   8   3 ]
[  24  19  14   9   4 ]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.