Fill a Special Grid solution and explanation
Google
7 more videos on this problem
3537. Fill a Special Grid| Contest 448Tech Courses · 15:52 · 715 views
Fill a Special Grid | LeetCode 3537 | Weekly Contest 448 | Java Code | Developer CoderDeveloper Coder · 15:34 · 527 views
Leetcode 3537 | Fill a Special Grid | Weekly Contest 448Road To FAANG · 17:46 · 390 views
3537 Fill a Special Grid | LeetCodeR Sai Siddhu · 18:31 · 343 views
LeetCode 3537. Fill a Special Grid | Recursion | O(R*C) | MediumLeet's Code · 22:10 · 181 views
3537. Fill a Special Grid (Leetcode Medium)Programming Live with Larry · 11:22 · 155 views
3537. Fill a Special Grid | Weekly Contest 448 | LeetcodeAmit Choraria · 15:59 · 142 views
Fill a Special Grid | LeetCode 3537 Explained Simply (Recursive NumPy Solution in Python)Machinelearningcode · 13:20 · 22 views
The 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:
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.
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 ansclass 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;
}
};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;
}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
}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
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation | O(n²) | O(1) | Useful for small grids or when implementing the rule directly per cell |
| Divide and Conquer Quadrant Fill | O(n²) | O(log n) | Best approach when the grid pattern repeats recursively across submatrices |
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).