# Fill a Special Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/fill-a-special-grid)
Canonical: https://scaleengineer.com/dsa/problems/fill-a-special-grid
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
**Data structures:** Array, Matrix
---
## Problem
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:**

![](https://assets.glich.co/dsa/fill-a-special-grid/image0.png)

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`

# Approaches
## Direct Calculation using Bit Manipulation
This approach calculates the value for each cell `(r, c)` of the grid independently. The core idea is that the value at any cell is determined by which quadrant it falls into at each level of recursion, from the largest `2^n x 2^n` grid down to a `1x1` grid. This can be mapped to the binary representations of the row `r` and column `c` indices.
**Time:** O(n * 4^n) - We iterate through `4^n` cells, and for each cell, we perform a loop of `n` iterations to calculate its value. · **Space:** O(4^n) - We need to store the final `2^n x 2^n` grid. The space used by variables within the loops is negligible.
**Pros:** Each cell's value is computed independently, which could be parallelized.; Avoids recursion and the potential for stack overflow (though not an issue with the given constraints).
**Cons:** Less efficient than the recursive construction approach due to the extra factor of `n` in the time complexity.; It re-calculates information for each cell instead of building upon previous results.
### Explanation
The value at `grid[r][c]` can be expressed as a sum: `value = Σ (Q_i * 4^i)` for `i` from `0` to `n-1`.

`Q_i` is a "quadrant multiplier" determined by the `i`-th bits of `r` and `c`, let's say `r_i` and `c_i`. The pair `(r_i, c_i)` corresponds to a quadrant at the `i`-th level of subdivision. The multipliers are derived from the problem's ordering constraint (`TR < BR < BL < TL`):
- `(0, 1)` (Top-Right): Multiplier `0`
- `(1, 1)` (Bottom-Right): Multiplier `1`
- `(1, 0)` (Bottom-Left): Multiplier `2`
- `(0, 0)` (Top-Left): Multiplier `3`

The algorithm iterates through each cell `(r, c)` of the `2^n x 2^n` grid. For each cell, it iterates from `i = 0` to `n-1`, extracts the `i`-th bits of `r` and `c`, determines the multiplier `Q_i`, and adds `Q_i * 4^i` to the total value for that cell.

```java
class Solution {
    public int[][] fillSpecialGrid(int n) {
        int dim = 1 << n; // 2^n
        int[][] grid = new int[dim][dim];

        for (int r = 0; r < dim; r++) {
            for (int c = 0; c < dim; c++) {
                int value = 0;
                long powerOf4 = 1;
                for (int i = 0; i < n; i++) {
                    int r_bit = (r >> i) & 1;
                    int c_bit = (c >> i) & 1;
                    int multiplier;
                    if (r_bit == 0 && c_bit == 0) { // Top-Left in sub-grid
                        multiplier = 3;
                    } else if (r_bit == 0 && c_bit == 1) { // Top-Right
                        multiplier = 0;
                    } else if (r_bit == 1 && c_bit == 0) { // Bottom-Left
                        multiplier = 2;
                    } else { // Bottom-Right
                        multiplier = 1;
                    }
                    value += multiplier * powerOf4;
                    powerOf4 *= 4;
                }
                grid[r][c] = value;
            }
        }
        return grid;
    }
}
```
### Algorithm
- Calculate the grid dimension `dim = 2^n`.
- Create an empty `dim x dim` integer grid `result`.
- Loop for `r` from `0` to `dim - 1`.
- Loop for `c` from `0` to `dim - 1`.
- For each cell `(r, c)`, calculate its value using a helper function based on bit manipulation:
  - Initialize `cellValue = 0` and `powerOf4 = 1`.
  - Loop for `i` from `0` to `n - 1`.
  - Extract the `i`-th bit of `r` (`r_i`) and `c` (`c_i`).
  - Determine the quadrant multiplier `Q` based on the pair `(r_i, c_i)`:
    - `(0, 1)` (Top-Right) -> `Q=0`
    - `(1, 1)` (Bottom-Right) -> `Q=1`
    - `(1, 0)` (Bottom-Left) -> `Q=2`
    - `(0, 0)` (Top-Left) -> `Q=3`
  - Add `Q * powerOf4` to `cellValue`.
  - Update `powerOf4` by multiplying it by 4.
- Assign the calculated `cellValue` to `result[r][c]`.
- Return `result`.

## Recursive Divide and Conquer
This approach leverages the inherent recursive structure of the "special" grid definition. A special grid of size `2^n x 2^n` is composed of four special sub-grids of size `2^(n-1) x 2^(n-1)`. We can solve the problem for `n-1` and use that solution to construct the solution for `n`.
**Time:** O(4^n) - Let `T(k)` be the time to compute the grid for `n=k`. The recurrence relation is `T(k) = T(k-1) + O(4^k)`, as we make one recursive call and then iterate through `4^(k-1)` cells to fill the four quadrants of the new grid. This solves to `O(4^n)`, which is linear in the number of cells in the output grid. · **Space:** O(4^n) - The recursion depth is `n`. At each level of recursion, a new grid is created. The total space is the sum of the sizes of all grids in the call stack: `Σ 4^k` for `k=0 to n`, which is `O(4^n)`. The space is dominated by the final grid.
**Pros:** Optimal time complexity, as every cell must be visited at least once.; The logic directly follows the recursive definition of the problem, making it elegant and easy to understand.
**Cons:** Uses recursion, which can lead to stack overflow for very large `n` (not an issue here since `n <= 10`).; Creates intermediate grids at each step of the recursion, which can be memory-intensive.
### Explanation
The base case is `n=0`, where the grid is `[[0]]`.

For `n > 0`, we first recursively generate the special grid for `n-1`. Let's call this `subGrid`. This `subGrid` is of size `2^(n-1) x 2^(n-1)` and contains numbers from `0` to `4^(n-1) - 1`.

The total number of elements in each quadrant of the `2^n x 2^n` grid is `k = (2^(n-1))^2 = 4^(n-1)`. The problem states the number ranges for the quadrants must be `TR < BR < BL < TL`. This means we can partition the numbers `0` to `4^n - 1` into four blocks of size `k`.
- Top-Right (TR): `0` to `k-1`
- Bottom-Right (BR): `k` to `2k-1`
- Bottom-Left (BL): `2k` to `3k-1`
- Top-Left (TL): `3k` to `4k-1`

We can construct the final `2^n x 2^n` grid by placing modified versions of the `subGrid` into the four quadrants:
- TR: `subGrid` (values are already in the `0` to `k-1` range)
- BR: `subGrid` with `k` added to each element.
- BL: `subGrid` with `2k` added to each element.
- TL: `subGrid` with `3k` added to each element.

This process is implemented in a recursive function that builds the grid from the base case upwards.

```java
class Solution {
    public int[][] fillSpecialGrid(int n) {
        return solve(n);
    }

    private int[][] solve(int k) {
        if (k == 0) {
            return new int[][]{{0}};
        }

        // Recursively get the grid for n-1
        int[][] subGrid = solve(k - 1);
        
        int subDim = 1 << (k - 1); // 2^(k-1)
        int dim = 1 << k;          // 2^k
        int[][] result = new int[dim][dim];
        
        int offset = subDim * subDim; // 4^(k-1)

        for (int i = 0; i < subDim; i++) {
            for (int j = 0; j < subDim; j++) {
                // Top-Right Quadrant
                result[i][j + subDim] = subGrid[i][j];
                // Bottom-Right Quadrant
                result[i + subDim][j + subDim] = subGrid[i][j] + offset;
                // Bottom-Left Quadrant
                result[i + subDim][j] = subGrid[i][j] + 2 * offset;
                // Top-Left Quadrant
                result[i][j] = subGrid[i][j] + 3 * offset;
            }
        }
        
        return result;
    }
}
```
### Algorithm
- Define a recursive function `solve(k)` that returns a special grid for `n=k`.
- **Base Case:** If `k=0`, return `[[0]]`.
- **Recursive Step:** If `k > 0`:
  - Call `solve(k-1)` to get the `subGrid`.
  - Get the size of the sub-grid, `subDim = 2^(k-1)`.
  - Calculate the offset `offset = subDim * subDim`.
  - Create a new `2*subDim x 2*subDim` grid, `result`.
  - Iterate through the `subGrid` from `(i, j)` where `0 <= i, j < subDim`.
  - Populate the four quadrants of `result`:
    - `result[i][j + subDim] = subGrid[i][j]` (Top-Right)
    - `result[i + subDim][j + subDim] = subGrid[i][j] + offset` (Bottom-Right)
    - `result[i + subDim][j] = subGrid[i][j] + 2 * offset` (Bottom-Left)
    - `result[i][j] = subGrid[i][j] + 3 * offset` (Top-Left)
  - Return `result`.
- The main function simply calls `solve(n)`.