3 ms C code with O(1) swap space and O(n) time


  • 0
    A
    void rotate(int **matrix, int n) {
        
        
        //1111   ->   321
        //2222   ->   321 
        //3333   ->   321
        //4444
        
        if(n == 0 || n == 1){
            return;
        }
        
        int lastRow = n-1;
        int lastCol = n-1;
        
        int mid = n/2; 
        
        for(int row = 0 ; row <  mid ; row++){
            
            int innerMatrixFirstRow = row;
            int innerMatrixLastRow = lastRow - row ; 
            
            int innerMatrixFirstCol = row;
            int innerMatrixLastCol  = lastCol - row ;
            
            for(int col = row,  delta = 0  ; col < innerMatrixLastCol ; col++, delta++){
                
                //12
                //34
                
                //save 2 in swap1
                int swap1 = matrix[innerMatrixFirstRow + delta][innerMatrixLastCol]; 
                
                //overwrite 2 with 1 - 1 can be overwritten now
                matrix[innerMatrixFirstRow + delta ][innerMatrixLastCol] = matrix[innerMatrixFirstRow][innerMatrixFirstCol + delta];
                
                //save 4 in swap2
                int swap2 = matrix[innerMatrixLastRow][innerMatrixLastCol - delta];
                
                //overrite 4 with 2 
                matrix[innerMatrixLastRow][innerMatrixLastCol - delta] = swap1;
                
                //save 3 in swap3 
                int swap3 = matrix[innerMatrixLastRow - delta ][innerMatrixFirstCol];
                
                //overwrite 3 by 4
                matrix[innerMatrixLastRow - delta ][innerMatrixFirstCol]  = swap2;
                
                //overwrite 1 by 3
                matrix[innerMatrixFirstRow][innerMatrixFirstCol + delta]  = swap3;
                
                //31
                //42
                
            }
        }
    }

Log in to reply
 

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