3537. Fill a Special Grid LeetCode Solution

Last updated: May 5, 2025

In this guide, you will get 3537. Fill a Special Grid LeetCode Solution with the best time and space complexity. The solution to Fill a Special Grid problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Fill a Special Grid solution in C++
Fill a Special Grid solution in Java
Fill a Special Grid solution in Python
Additional Resources

3537. Fill a Special Grid LeetCode Solution image

Problem Statement of Fill a Special Grid

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 1×1 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

Complexity Analysis

Time Complexity: O(2^n \cdot 2^n)
Space Complexity: O(2^n \cdot 2^n)

3537. Fill a Special Grid LeetCode Solution in C++

class Solution {
 public:
  vector<vector<int>> specialGrid(int n) {
    const int sz = 1 << n;
    int count = 0;
    vector<vector<int>> grid(sz, vector<int>(sz));
    fill(grid, 0, sz, 0, sz, count);
    return grid;
  }

  void fill(vector<vector<int>>& grid, int x1, int x2, int y1, int y2,
            int& count) {
    if (x2 - x1 == 1) {
      grid[x1][y1] = count++;
      return;
    }
    const int midRow = (x1 + x2) / 2;
    const int midCol = (y1 + y2) / 2;
    fill(grid, x1, midRow, midCol, y2, count);
    fill(grid, midRow, x2, midCol, y2, count);
    fill(grid, midRow, x2, y1, midCol, count);
    fill(grid, x1, midRow, y1, midCol, count);
  }
};
/* code provided by PROGIEZ */

3537. Fill a Special Grid LeetCode Solution in Java

class Solution {
  public int[][] specialGrid(int n) {
    final int sz = 1 << n;
    int[][] grid = new int[sz][sz];
    fill(grid, 0, sz, 0, sz);
    return grid;
  }

  private int count = 0;

  private void fill(int[][] grid, int x1, int x2, int y1, int y2) {
    if (x2 - x1 == 1) {
      grid[x1][y1] = count++;
      return;
    }
    int midRow = (x1 + x2) / 2;
    int midCol = (y1 + y2) / 2;
    fill(grid, x1, midRow, midCol, y2);
    fill(grid, midRow, x2, midCol, y2);
    fill(grid, midRow, x2, y1, midCol);
    fill(grid, x1, midRow, y1, midCol);
  }
}
// code provided by PROGIEZ

3537. Fill a Special Grid LeetCode Solution in Python

class Solution:
  def specialGrid(self, n: int) -> list[list[int]]:
    sz = 1 << n
    grid = [[0] * sz for _ in range(sz)]
    count = 0

    def fill(x1: int, x2: int, y1: int, y2: int) -> None:
      nonlocal count
      if x2 - x1 == 1:
        grid[x1][y1] = count
        count += 1
        return
      midRow = (x1 + x2) // 2
      midCol = (y1 + y2) // 2
      fill(x1, midRow, midCol, y2)
      fill(midRow, x2, midCol, y2)
      fill(midRow, x2, y1, midCol)
      fill(x1, midRow, y1, midCol)

    fill(0, sz, 0, sz)
    return grid
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents