Skip to main content
Talentd

Fill a Special Grid - Solution & Explanation

MediumArrayDivide and ConquerMatrix10 min readAsked at: Google
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You need to construct a matrix that follows a specific ordering rule across its cells. The grid is built so that values increase according to a structured pattern, and the pattern repeats recursively across sub‑grids. The challenge is recognizing that the grid can be divided into smaller blocks that follow the same ordering rule.

Approach 1: Direct Simulation with Iterative Placement (O(n2) time, O(1) extra space)

The most straightforward idea is to iterate over every cell in the matrix and place values according to the required rule. You compute which region the cell belongs to and assign numbers in the correct order. This works because every position is visited exactly once. However, the logic for determining the correct value per cell can become messy as grid size grows, especially when the ordering rule depends on recursive structure. This approach is useful for understanding the pattern but not ideal for clean implementation.

Approach 2: Divide and Conquer on Matrix Quadrants (O(n2) time, O(log n) recursion space)

The grid structure reveals a repeating pattern across quadrants. Split the matrix into four equal subgrids, solve the same problem for each quadrant, and offset the values based on the quadrant index. Each recursive step fills a smaller n/2 × n/2 matrix, while maintaining the global ordering by adding the correct base value. The recursion stops when the grid reaches the base case (typically 1 × 1). Because each cell is written exactly once, total work remains linear in the number of cells.

This pattern is common in problems involving divide and conquer on a matrix. Instead of computing each cell independently, you build the grid hierarchically. The key insight is that each quadrant contains a contiguous range of values, which lets you reuse the same logic recursively.

Recommended for interviews: The divide and conquer approach is what interviewers typically expect. A brute or simulation solution demonstrates that you understand the pattern, but the recursive quadrant construction shows stronger algorithmic thinking and familiarity with array and matrix decomposition techniques.

Solution

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct SimulationO(n²)O(1)Useful for small grids or when implementing the rule directly per cell
Divide and Conquer Quadrant FillO(n²)O(log n)Best approach when the grid pattern repeats recursively across submatrices

Video Solution

3537. Fill a Special Grid| Contest 448 • Tech Courses • 715 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Fill a Special Grid easy or hard?
Fill a Special Grid is generally considered a medium difficulty problem. The implementation itself is not long, but recognizing the recursive quadrant structure is the key insight that makes the problem straightforward.
Fill a Special Grid Python/Java solution
A typical implementation creates a 2D array and fills it using a recursive helper that processes quadrants. The same logic works across Python, Java, C++, and Go by passing the current subgrid boundaries and value offset during recursion.
How to solve Fill a Special Grid in O(n^2)?
Construct the matrix using recursive quadrant decomposition. For an n × n grid, divide it into four n/2 × n/2 subgrids, fill each recursively, and add a value offset so each quadrant receives the correct range of numbers. Since each cell is assigned once, the algorithm runs in O(n^2).
What is the best approach for Fill a Special Grid?
The most efficient approach uses divide and conquer on the matrix. Split the grid into four equal quadrants, recursively fill each subgrid, and offset values based on the quadrant order. This keeps the implementation clean and ensures every cell is written once, giving O(n^2) time complexity.
Is Fill a Special Grid asked at Google/Amazon/Meta?
Problems involving recursive matrix construction and divide-and-conquer patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require filling grids or traversing matrix quadrants are common in system and algorithm interviews.
What data structure is used in Fill a Special Grid?
The main data structure is a 2D array (matrix). The algorithm also relies on recursion from the divide and conquer paradigm to process smaller submatrices and combine them into the final grid.
What is the time complexity of Fill a Special Grid?
The optimal algorithm runs in O(n^2) time because every cell in the matrix must be filled exactly once. The divide and conquer recursion simply organizes how the cells are filled but does not increase the total work. Recursion depth is typically O(log n).

Ready to solve this problem?

Practice Fill a Special Grid with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays