3537. Fill a Special Grid

You are given a non-negative integer N representing a 2N x 2N grid. You must fill the grid with integers from 0 to 22N - 1 to make it special. A grid is special if it satisfies all the following conditions:

• All numbers in the top-right quadrant are smaller than those in the bottom-right quadrant.
• All numbers in the bottom-right quadrant are smaller than those in the bottom-left quadrant.
• All numbers in the bottom-left quadrant are smaller than those in the top-left quadrant.
• Each of its quadrants is also a special grid.

Return the special 2N x 2N grid.

Note: Any 1x1 grid is special.

Divide and Conquer

class Solution {
    void dnc(vector<vector<int>>& res, int y, int x, int len, int& ord) {
        if(len == 1) res[y][x] = ord++;
        else {
            len>>=1;
            dnc(res, y, x + len, len, ord);
            dnc(res, y + len, x + len, len, ord);
            dnc(res, y + len, x, len, ord);
            dnc(res, y, x, len, ord);
        }
    }
public:
    vector<vector<int>> specialGrid(int N) {
        int n = 1<<N, ord = 0;
        vector<vector<int>> res(n, vector<int>(n));
        dnc(res, 0,0,n, ord);
        return res;
    }
};

Math + Bit Manipulation

class Solution {
public:
    vector<vector<int>> specialGrid(int N) {
        int size = 1 << N;
        vector<vector<int>> res(size, vector<int>(size, 0));
        int table[2][2] {{3, 0}, {2, 1}};
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                for(int k = N - 1; k >= 0; k--) {
                    res[i][j] = (res[i][j]<<2) + table[(i >> k) & 1][(j >> k) & 1];
                }
            }
        }
        return res;
    }
};