My in-place, one pass solution with 4-way move (Java) with comments and explanation


  • 0
    W

    The idea is to "peel the onion", and move one layer at a time moving inwards. For an NxN matrix, there are N/2 such layers to move. The complicated thing is to come up with the proper offset and math for the swaps.

    public void rotate(int[][] matrix) {
            if (matrix.length == 0 || matrix[0].length == 0) return;
            int n = matrix.length;
            int rounds = n / 2;
            
            for (int j = 0; j < rounds; j++) {
                int first = j;
                int last = n - j - 1;
                for (int i = first; i < last; i++) {
                    int offset = i - first;
    
                    //save top
                    int top = matrix[first][i];
    
                    //left -> top
                    matrix[first][i] = matrix[last - offset][first];
    
                    //bottom -> left
                    matrix[last - offset][first] = matrix[last][last - offset];
    
                    //right -> bottom
                    matrix[last][last - offset] = matrix[i][last];
    
                    //top -> right
                    matrix[i][last] = top;
                }
            }
        }
    

Log in to reply
 

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