A different idea, explained simple C++ solution in 4ms


  • 0
    M

    Someone may talked about this before, I just post my experience here.

    The tricky idea is: Before we turn the direction, we already know the the running length for every direction. Because they are in order. For example, when n=5, the running length are 5,4,4,3,3,2,2,1,1. We can express it by using n, the running length are n,n-1,n-1,n-2,n-2...2,2,1,1.

    (If it's m*n rectangle, it would be n,m-1,n-1,m-2,n-2....)

    Another point is that, when we turn direction, one coordinate is fixed, we just need to change another one. If the coordinate is (i, j),
    when turn right: i is fixed, j will increase(j++);
    when turn down: j is fixed, i will increase(i++);
    when turn left: i is fixed, j will decrease(j--);
    when turn up: j is fixed, i will decrease(i--);

    Simple code:

    class Solution {
    public:
        vector<vector<int>> generateMatrix(int n) {
            vector<vector<int>> ans(n, vector<int>(n,1));        
            if(n<=1) return ans;
            int lastLength=n, curLength=n;  //running length
            int i=0, j=-1;                  //coordinate
            int dire=0, val=1;              //direction, value
            while(curLength)
            {
                for(int cnt=curLength; cnt>0; cnt--)
                {   
                    if(dire==0) j++;        //0 -> right
                    else if(dire==1) i++;   //1 -> down
                    else if(dire==2) j--;   //2 -> left
                    else if(dire==3) i--;   //3 -> up
                    ans[i][j]=val++;
                }
                dire= (dire+1)%4;
                swap(--lastLength, curLength); //tricky here
            }
            return ans;
        }
    };
    

    Old version:

    class Solution {
    public:
        vector<vector<int>> generateMatrix(int n) {
            vector<vector<int>> ans(n, vector<int>(n,1));        
            if(n<=1) return ans;
            int lastLength=n, curLength=n;  //running length
            int i=0, j=-1;                  //coordinate
            int dire=0, val=1;              //direction, value
            while(curLength)
            {
                if(dire==0)                                 //0 -> right
                    for(int cnt=curLength; cnt>0; cnt--)
                        ans[i][++j]=val++;
                if(dire==1)                                 //1 -> down
                    for(int cnt=curLength; cnt>0; cnt--) 
                        ans[++i][j]=val++;
                if(dire==2)                                 //2 -> left
                    for(int cnt=curLength; cnt>0; cnt--)
                        ans[i][--j]=val++;
                if(dire==3)                                 //3 -> up
                    for(int cnt=curLength; cnt>0; cnt--)
                        ans[--i][j]=val++;
                dire= (dire+1)%4;
                if(lastLength!=curLength) lastLength--; //tricky here
                else curLength--;
            }
            return ans;
        }
    };

Log in to reply
 

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