c++ 4ms solution


  • 1
    J

    The basic idea is simple, whenever the element is not 0, or the boundaries is crossed, changing traversing direction spirally.
    Using a vector of pair to indicate directions.

    class Solution {
    public:
        vector<vector<int>> generateMatrix(int n) {
            vector<pair<int, int>> dir{make_pair(0, 1), make_pair(1, 0), make_pair(0, -1), make_pair(-1, 0)};
            vector<vector<int>> ret(n, vector<int>(n, 0));
            int idx = 0;
            int i = 0, j = 0, val = 1, sq = n * n;
            while(val <= sq) {
                if(i >= 0 && i < n && j >= 0 && j < n && ret[i][j] == 0) {
                    ret[i][j] = val++;
                    i += dir[idx % 4].first;
                    j += dir[idx % 4].second;
                }
    
                if(!(i >= 0 && i < n && j >= 0 && j < n && ret[i][j] == 0)) {
                    i -= dir[idx % 4].first;
                    j -= dir[idx % 4].second;
                    idx++;
                    i += dir[idx % 4].first;
                    j += dir[idx % 4].second;
                }
            }
            return ret;
        }
    };
    

Log in to reply
 

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