Fill a Special Grid - Practice Coding Problems

Fill a Special Grid - Problem

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.

Input & Output

Example 1 — Base Case

$ Input: n = 0

› Output: [[0]]

💡 Note: A 2^0 x 2^0 = 1x1 grid with single element 0. Any 1x1 grid is special by definition.

Example 2 — Small Grid

$ Input: n = 1

› Output: [[3,0],[2,1]]

💡 Note: A 2^1 x 2^1 = 2x2 grid. Quadrants: TR=0, BR=1, BL=2, TL=3. Satisfies 0 < 1 < 2 < 3.

Example 3 — Larger Grid

$ Input: n = 2

› Output: [[15,14,3,2],[13,12,1,0],[11,10,7,6],[9,8,5,4]]

💡 Note: A 4x4 grid where each 2x2 quadrant is special and follows the ordering: TR < BR < BL < TL

Constraints

0 ≤ n ≤ 6
Grid size will be 2ⁿ x 2ⁿ
Numbers range from 0 to 2²ⁿ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Integer n representing grid size 2^n x 2^n

Process

Fill grid maintaining quadrant ordering: TR < BR < BL < TL

Output

Special grid where each quadrant is recursively special

Key Takeaway

🎯 Key Insight: Use divide and conquer with proper value range assignment to maintain quadrant ordering at every level

Asked in

G Google 25 M Microsoft 20 a Amazon 18 f Facebook 15

The key insight is to use divide and conquer with proper value range assignment. Each quadrant gets a specific range: top-right (smallest) < bottom-right < bottom-left < top-left (largest), then recursively fill each quadrant. Best approach is divide and conquer with Time: O(2^(2n)), Space: O(2^(2n)).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Permutations	O((2^(2n))!)	O(2^(2n))	Generate all possible arrangements and check special conditions
Divide and Conquer - Recursive Quadrants	O(2^(2n))	O(2^(2n))	Recursively fill quadrants with proper value offsets

Brute Force - Try All Permutations — Algorithm Steps

Generate all permutations of numbers 0 to 2^(2n)-1
For each permutation, fill the grid
Check if all quadrant ordering conditions are satisfied
Check if each quadrant is recursively special
Return the first valid arrangement

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Create all possible arrangements of numbers 0 to 2^(2n)-1

Fill Grid

Place each permutation into the 2^n x 2^n grid

Validate

Check if grid satisfies all special conditions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int** solution(int n, int* returnSize, int** returnColumnSizes) {
    if (n == 0) {
        *returnSize = 1;
        *returnColumnSizes = malloc(sizeof(int));
        (*returnColumnSizes)[0] = 1;
        int** result = malloc(sizeof(int*));
        result[0] = malloc(sizeof(int));
        result[0][0] = 0;
        return result;
    }
    
    int size = 1 << n;
    *returnSize = size;
    *returnColumnSizes = malloc(size * sizeof(int));
    
    int** grid = malloc(size * sizeof(int*));
    int num = 0;
    
    for (int i = 0; i < size; i++) {
        (*returnColumnSizes)[i] = size;
        grid[i] = malloc(size * sizeof(int));
        for (int j = 0; j < size; j++) {
            grid[i][j] = num++;
        }
    }
    
    return grid;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(n, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((2^(2n))!)

Generates all permutations of 2^(2n) numbers and validates each

✓ Linear Growth

Space Complexity

O(2^(2n))

Stores the grid and permutation arrays

⚡ Linearithmic Space

35.6K Views

Medium Frequency

~30 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler