Quirky In-Place Single-Swap Solution


  • 0
    G

    The idea is that we can push items around the perimeter of the matrix until they're in place, then descend into the next layer in the matrix and repeat.

    Here's a derpy drawing I made to convey that idea.
    Rotating the Matrix

    This approach gets 3ms on the LeetCode tests.

    The legibility of the implementation, I think, can be much improved.

    public class Solution {
        // The current n x n matrix
        private int n;
        
        /**
         * Returns the [i] and [j] indices for the original matrix, given the
         * rotational index i, and the depth d from the outside.
         * 
         * @param i, the ith clockwise index of the perimeter of the current matrix
         * @param d, the depth into the given matrix
         * @return 
         */
        public int[] cycleIndex(int i, int d) {
            i %= 4 * (n - 1);
            
            int[] ij = new int[2];
            
            // top
            if (i < n) {
                ij[0] = d;
                ij[1] = i + d;
            }
            
            // right
            else if (i < 2 * n - 1) {
                ij[0] = 1 + i - n + d;
                ij[1] = n - 1 + d;
            }
            
            // bottom
            else if (i < 3 * n - 2) {
                ij[0] = n - 1 + d;
                ij[1] = n - 1 - (i - (2 * n - 2)) + d;
            }
            
            // left
            else {
                ij[0] = n - 1 - (i - (3 * n - 3)) + d;
                ij[1] = d;
            }
            return ij;
        }
        
        public void rotate(int[][] matrix) {
            n = matrix.length;
            
            // Stores i, j indices
            int[] tmp;
            
            // Our queue structure
            int back, front;
            
            
            // Keep track of depth into matrix, from perimeter
            for (int d = 0; n > 1; d++) {
                
                // Will have (n-1) four-cycles
                for (int j = 0; j < n - 1; j++) {
                    
                    // Initialize our two-element queue
                    tmp = cycleIndex(j + 3 * (n - 1), d);
                    front = matrix[tmp[0]][tmp[1]];
                    
                    // Complete a four-cycle
                    for (int i = j; i < 4 * (n - 1); i += (n - 1)) {
                        tmp = cycleIndex(i, d);
                        back = matrix[tmp[0]][tmp[1]];
                        matrix[tmp[0]][tmp[1]] = front;
                        front = back;
                    }
                }
                n -= 2;
            }
        }
    }
    

    Given the following matrix:

    {{1,2,3,2,1},
     {2,3,4,3,2},
     {3,4,5,4,3},
     {4,5,6,5,4},
     {5,6,7,6,5}}
    

    below are the completed four-cycles of this algorithm.

    j = 0
    {{5,2,3,2,1},
     {2,3,4,3,2},
     {3,4,5,4,3},
     {4,5,6,5,4},
     {5,6,7,6,1}}
    
    j = 1
    {{5,4,3,2,1},
     {2,3,4,3,2},
     {3,4,5,4,3},
     {6,5,6,5,4},
     {5,6,7,2,1}}
    
    j = 2
    {{5,4,3,2,1},
     {2,3,4,3,2},
     {7,4,5,4,3},
     {6,5,6,5,4},
     {5,6,3,2,1}}
    
    j = 3
    {{5,4,3,2,1},
     {6,3,4,3,2},
     {7,4,5,4,3},
     {6,5,6,5,2},
     {5,4,3,2,1}}
    
    d = 1; j = 0
    {{5,4,3,2,1},
     {6,5,4,3,2},
     {7,4,5,4,3},
     {6,5,6,3,2},
     {5,4,3,2,1}}
    
    j = 1
    {{5,4,3,2,1},
     {6,5,4,3,2},
     {7,6,5,4,3},
     {6,5,4,3,2},
     {5,4,3,2,1}}
    

Log in to reply
 

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