Welcome to Subscribe On Youtube

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

  • 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);
    }
}

  • 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;
    }
};

  • 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


  • 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
}


  • 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;
}


  • 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
    }
}

All Problems

All Solutions