Neat C++ Solution - 6ms


  • 1
    A

    Direction switching without using additional structures. Easy to follow without any flow control in the main loop body. The fill function is inlined by the compiler, so there is no overhead:

    typedef vector<int> VI;
    typedef vector<VI> VVI;
    
    VVI generateMatrix(int n) {
        VVI m(n, VI(n));
        int idx = 1;    // Current index
        int l = 0;      // Spiral layer
        int len = n;    // Upper horizontal edge length
        while (len > 0) {
    		fill(len, l, l, 0, 1, &idx, &m);
    		fill(len-1, l+1, n-l-1, 1, 0, &idx, &m);
    		fill(len-1, n-l-1, n-l-2, 0, -1, &idx, &m);
    		fill(len-2, n-l-2, l, -1, 0, &idx, &m); 
    		++l; 
    		len -= 2;
        }
    	return m;
    }
    
    /** Fills 'count' numbers in the spiral following the direction */
    void fill(int count, int i, int j, int di, int dj, int* idx, VVI* m) {
        while (count-- > 0) {
            (*m)[i][j] = (*idx)++;
            i += di;
            j += dj;
        }
    }

Log in to reply
 

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