Fill a Special Grid

Med

#3148Time: 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.

Algorithms

Divide and Conquer

Data structures

Array Matrix

Prompt

You are given a non-negative integer n representing a 2ⁿ x 2ⁿ grid. You must fill the grid with integers from 0 to 2²ⁿ - 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 2ⁿ x 2ⁿ 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

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public int[][] fillSpecialGrid(int n) {3        int dim = 1 << n; // 2^n4        int[][] grid = new int[dim][dim];5 6        for (int r = 0; r < dim; r++) {7            for (int c = 0; c < dim; c++) {8                int value = 0;9                long powerOf4 = 1;10                for (int i = 0; i < n; i++) {11                    int r_bit = (r >> i) & 1;12                    int c_bit = (c >> i) & 1;13                    int multiplier;14                    if (r_bit == 0 && c_bit == 0) { // Top-Left in sub-grid15                        multiplier = 3;16                    } else if (r_bit == 0 && c_bit == 1) { // Top-Right17                        multiplier = 0;18                    } else if (r_bit == 1 && c_bit == 0) { // Bottom-Left19                        multiplier = 2;20                    } else { // Bottom-Right21                        multiplier = 1;22                    }23                    value += multiplier * powerOf4;24                    powerOf4 *= 4;25                }26                grid[r][c] = value;27            }28        }29        return grid;30    }31}

Complexity

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.

Trade-offs

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.

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.

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).

Walkthrough

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.

1class Solution {2    public int[][] fillSpecialGrid(int n) {3        return solve(n);4    }5 6    private int[][] solve(int k) {7        if (k == 0) {8            return new int[][]{{0}};9        }10 11        // Recursively get the grid for n-112        int[][] subGrid = solve(k - 1);13        14        int subDim = 1 << (k - 1); // 2^(k-1)15        int dim = 1 << k;          // 2^k16        int[][] result = new int[dim][dim];17        18        int offset = subDim * subDim; // 4^(k-1)19 20        for (int i = 0; i < subDim; i++) {21            for (int j = 0; j < subDim; j++) {22                // Top-Right Quadrant23                result[i][j + subDim] = subGrid[i][j];24                // Bottom-Right Quadrant25                result[i + subDim][j + subDim] = subGrid[i][j] + offset;26                // Bottom-Left Quadrant27                result[i + subDim][j] = subGrid[i][j] + 2 * offset;28                // Top-Left Quadrant29                result[i][j] = subGrid[i][j] + 3 * offset;30            }31        }32        33        return result;34    }35}

Complexity

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.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem