Iterative rotate matrix similar to rotating picture


  • 0
    L

    // The idea is to go layer by layer like circles inside circles:
    // at each layer assign 4 sides of a square
    // for eg. for 4x4 matrix, left-> right is 1,2,3 up->down is 4,5,6, right->left is 7,8,9 and so on..
    // So we start assigning each corner, each corner is layerwidth more than previous.

    vector<vector<int> > generateMatrix(int n) {
            vector<vector<int>> result(n, vector<int>(n, 1));
            // r: layer (also starting row and column)
            // rend: where that layer should end
            // narrow down till 1(if n is odd only center element is left) or 0 elements
            // c iterates n-1 items in 4 directions left->right, up->down, right->left, down->up
            for (int i=1, r=0, rend = n-1; r<rend; r++, rend--) {
                int diff = rend - r;
                for (int c=r; c<rend; c++, i++) {
                    result[r][c] = i;
                    result[c][rend] = result[r][c] + diff;
                    result[rend][n-c-1] = result[c][rend] + diff;
                    result[n-c-1][r] = result[rend][n-c-1] + diff;
                }
                i += diff * 3;
            }
            // if center element is left assign it.
            if (n%2)
                result[n/2][n/2] = n*n;
            return result;
        }

Log in to reply
 

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