Walking around each layer (3ms)


  • 0

    This is a bit overly complicated, but an in-place solution where you use a pointer and walk around the rim of the matrix and shift values around. When a layer of the matrix is done, we move inside and start again. For a 4x4 matrix it only required 16 loops, so its not super wasteful.

    public class Solution {
        public void rotate(int[][] matrix) {
            // Used to transmit data
            int [] coords = new int[3];
    
            // We will start at the outside and work out way in
            final int layers = matrix.length / 2;
    
            for (int layer = 0; layer < layers; layer++) {
                // How far to travel with each iteration
                int stride = (matrix.length) - (layer * 2) - 1;
                // Target the first location of this layer, the first location will be at [layer, layer]
                coords[0] = layer;
                coords[1] = layer;
                // We need to loop for all the possible points
                for (int a = 0; a < stride; a++) {
                    // The value to shift
                    int carry = matrix[coords[1]][coords[0]];
                    for (int b = 0; b < 4; b++) {
                        // shift the coordinate by it's stride
                        nextCoordinateFor(matrix, layer, stride,  coords);
    
                        // Debug Info
                        //System.out.println("Layer: " + layer);
                        //System.out.println("Stride: " + stride);
                        //System.out.println("A: " + a);
                        //System.out.println("B: " + b);
                        
                        // The value we're replacing
                        int nextCarry = matrix[coords[1]][coords[0]];
                        //System.out.println("Next: " + nextCarry);
                        // Overwrite this location with our carried value
                        matrix[coords[1]][coords[0]] = carry;
                        //System.out.println("Write: " + carry);
                        // Save the previous value for the next carry
                        carry = nextCarry;
    
                        //print(matrix, coords);
                    }
                    // Shift by 1, so we can get into the next stride
                    nextCoordinateFor(matrix, layer, 1,  coords);
                }
            }
    
        }
    
        /**
         * Thiw will map a new location around our virtual layer based upon the stride information.  We always travel
         * clockwise around the matrix, with [0,]0 being the top left position and [n-1, n-1] being the bottom right.
         * The idea is to use the stride information to move the coords to a new location around the edge of the layer.
         * The stride will never exced one layer jump so the logic doesn't need to be recursive.
         */
        public void nextCoordinateFor(int[][] matrix, int layer, int stride, int [] coords) {
    
            // Convert the coordinate to virtual space
            if (layer > 0) {
                // Shift over by layer, so 1,1 becomes 0,0 for layer 1
                coords[0] -= layer;
                coords[1] -= layer;
            }
    
            // we need to move along and find the next coordinate
    
            // The width is the matrix length - layer * 2, the reason for 2 is we remove 2 edges with every layer
            int layerWidth = matrix.length - (layer * 2);
    
            if (coords[1] == 0) { // we are on the top edge
                coords[0] += stride;
                if (coords[0] >= layerWidth) {
                    // We need to turn downward
                    coords[1] = coords[0] - (layerWidth - 1);
                    // On the right edge
                    coords[0] = layerWidth - 1;
                }
            } else if (coords[0] == layerWidth - 1) { // We are on the right edge
                coords[1] += stride;
                if (coords[1] >= layerWidth) {
                    // We need to turn left
                    coords[0] = (layerWidth - 1) - (coords[1] - (layerWidth - 1));
                    // On the bottom edge
                    coords[1] = layerWidth - 1;
                }
            } else if (coords[1] == layerWidth - 1) { // we are on the bottom edge
                coords[0] -= stride;
                if (coords[0] < 0) {
                    // We need to turn upward
                    coords[1] = (layerWidth - 1) + coords[0];
                    // On the left edge
                    coords[0] = 0;
                }
            } else if (coords[0] == 0) { // We are on the left edge
                coords[1]-= stride;
                if (coords[1] < 0) {
                    // We need to turn right
                    coords[0] = -coords[1];
                    // Back to the top layer
                    coords[1] = 0;
                }
            }
    
            // Convert the coordinate to actual space
            if (layer > 0) {
                // Shift over by layer, so 0,0 becomes 1,1 for layer 1
                coords[0] += layer;
                coords[1] += layer;
            }
        }
    
        // Debug Code
        /*
        void print(int [][] matrix, int [] coords){
            for (int y = 0; y < matrix.length; y++) {
                System.out.print("[");
                for (int x = 0; x < matrix.length; x++) {
                    if (x > 0)
                    System.out.print(",");
                    if (coords[0] == x && coords[1] == y) System.out.print("("); else System.out.print(" ");
    
                    int v = matrix[y][x];
                    if (v < 10) {
                        System.out.print(" ");
                    }
                    System.out.print(v);
    
                    if (coords[0] == x && coords[1] == y) System.out.print(")"); else System.out.print(" ");
                }
                System.out.println("]");
            }
        }
        */
        
    }
    

Log in to reply
 

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