Skip to content

3537. Fill a Special Grid

Description

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.

Β 

Example 1:

Input: n = 0

Output: [[0]]

Explanation:

The only number that can be placed is 0, and there is only one possible position in the grid.

Example 2:

Input: n = 1

Output: [[3,0],[2,1]]

Explanation:

The numbers in each quadrant are:

  • Top-right: 0
  • Bottom-right: 1
  • Bottom-left: 2
  • Top-left: 3

Since 0 < 1 < 2 < 3, this satisfies the given constraints.

Example 3:

Input: n = 2

Output: [[15,12,3,0],[14,13,2,1],[11,8,7,4],[10,9,6,5]]

Explanation:

The numbers in each quadrant are:

  • Top-right: 3, 0, 2, 1
  • Bottom-right: 7, 4, 6, 5
  • Bottom-left: 11, 8, 10, 9
  • Top-left: 15, 12, 14, 13
  • max(3, 0, 2, 1) < min(7, 4, 6, 5)
  • max(7, 4, 6, 5) < min(11, 8, 10, 9)
  • max(11, 8, 10, 9) < min(15, 12, 14, 13)

This satisfies the first three requirements. Additionally, each quadrant is also a special grid. Thus, this is a special grid.

Β 

Constraints:

  • 0 <= n <= 10

Solutions

Solution 1: Recursive Divide and Conquer

A special grid requires that in each quadrant, numbers satisfy: top-right < bottom-right < bottom-left < top-left, and each quadrant is also a special grid. We can construct it recursively: for a subgrid of size \(k\), fill the four quadrants in order "top-right β†’ bottom-right β†’ bottom-left β†’ top-left", ensuring smaller numbers are placed in the top-right quadrant first and larger numbers in the top-left quadrant last.

We start from the top-right corner \((0, m - 1)\) of the entire grid, where \(m = 2^n\), with side length \(m\). When \(k = 1\), we fill the cell with the current value and increment; otherwise, we split into four quadrants and recurse.

The time complexity is \(O(4^n)\), and the space complexity is \(O(4^n)\), where \(n\) is the input parameter.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def specialGrid(self, n: int) -> List[List[int]]:
        def dfs(x: int, y: int, k: int):
            if k == 1:
                nonlocal val
                ans[x][y] = val
                val += 1
                return

            dfs(x, y, k // 2)
            dfs(x + k // 2, y, k // 2)
            dfs(x + k // 2, y - k // 2, k // 2)
            dfs(x, y - k // 2, k // 2)

        m = 1 << n
        ans = [[0] * m for _ in range(m)]
        val = 0
        dfs(0, m - 1, m)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    private int[][] ans;
    private int val;

    public int[][] specialGrid(int n) {
        int m = 1 << n;
        ans = new int[m][m];
        dfs(0, m - 1, m);
        return ans;
    }

    private void dfs(int x, int y, int k) {
        if (k == 1) {
            ans[x][y] = val++;
            return;
        }

        int h = k / 2;
        dfs(x, y, h);
        dfs(x + h, y, h);
        dfs(x + h, y - h, h);
        dfs(x, y - h, h);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> specialGrid(int n) {
        int m = 1 << n;
        vector<vector<int>> ans(m, vector<int>(m));
        int val = 0;

        auto dfs = [&](this auto&& dfs, int x, int y, int k) -> void {
            if (k == 1) {
                ans[x][y] = val++;
                return;
            }

            int h = k / 2;
            dfs(x, y, h);
            dfs(x + h, y, h);
            dfs(x + h, y - h, h);
            dfs(x, y - h, h);
        };

        dfs(0, m - 1, m);
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func specialGrid(n int) [][]int {
    m := 1 << n
    ans := make([][]int, m)
    for i := range ans {
        ans[i] = make([]int, m)
    }
    val := 0

    var dfs func(int, int, int)
    dfs = func(x, y, k int) {
        if k == 1 {
            ans[x][y] = val
            val++
            return
        }

        h := k / 2
        dfs(x, y, h)
        dfs(x+h, y, h)
        dfs(x+h, y-h, h)
        dfs(x, y-h, h)
    }

    dfs(0, m-1, m)
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function specialGrid(n: number): number[][] {
    const m = 1 << n;
    const ans = Array.from({ length: m }, () => Array(m).fill(0));
    let val = 0;

    const dfs = (x: number, y: number, k: number): void => {
        if (k === 1) {
            ans[x][y] = val++;
            return;
        }

        const h = k >> 1;
        dfs(x, y, h);
        dfs(x + h, y, h);
        dfs(x + h, y - h, h);
        dfs(x, y - h, h);
    };

    dfs(0, m - 1, m);
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
impl Solution {
    pub fn special_grid(n: i32) -> Vec<Vec<i32>> {
        fn dfs(x: usize, y: usize, k: usize, ans: &mut Vec<Vec<i32>>, val: &mut i32) {
            if k == 1 {
                ans[x][y] = *val;
                *val += 1;
                return;
            }

            let h = k / 2;
            dfs(x, y, h, ans, val);
            dfs(x + h, y, h, ans, val);
            dfs(x + h, y - h, h, ans, val);
            dfs(x, y - h, h, ans, val);
        }

        let m = 1usize << n;
        let mut ans = vec![vec![0; m]; m];
        let mut val = 0;
        dfs(0, m - 1, m, &mut ans, &mut val);
        ans
    }
}

Comments