Java O(1n^2) Solution


  • 0
    A

    This solution visits all necessary elements starting from the top-left, and rotates it and the 3 other elements that correspond to it. Assuming x->y means "x moves to y's location", which can be chained, then for the following example:
    a b c => g d a
    d e f => h e b
    g h i => i f c

    a->c->i->g->a
    b->f->h->d->b

    Or, for the following example:
    a b c d => m i e a
    e f g h => n j f b
    i j k l => o k g c
    m n o p => p l h d

    a->d->p->m->a
    b->h->o->i->b
    c->l->n->e->c
    f->g->k->j->f

    If you observe the pattern you'll notice that we only need to visit half the rows (the other half will be rotated by the first half), and for each row we need to start the column at the same row (move diagonally down and right), and end the column starting at one less than n and moving diagonally down and left.

    Anyways, here's the code, with a bunch of variables (n, m, h, l) created to optimize performance. Since each full rotation requires 4 swaps, t keeps the original value of the first element, then we pull the appropriate value into the first element's location, and jump back to that pull-location and repeat the process 3 times. By then the last swap's value will be t.

    public void rotate(int[][] matrix) {
        final int n = matrix.length;
        final int m = n-1;
        final int h = n/2;
        for(int r=0, l=m; r < h; r++, l--) {
            for(int c=r; c < l; c++) {
                final int t = matrix[r][c];
                int cr=r, cc=c;
                for(int pr=m-cc, pc=cr, x=0; x < 3; cr=pr, cc=pc,pr=m-cc,pc=cr,x++)
                    matrix[cr][cc] = matrix[pr][pc];
                matrix[cr][cc] = t;
            }
        }
    }
    

Log in to reply
 

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