Scale Engineer

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
ArrayMatrix

Prompt

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

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.

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

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.

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 →

Next problem