Construct Quad Tree

MEDIUM✓ CHIP-TIMEDLC #427 — FULL STATEMENT ↗

The drill: Compress a 0/1 grid into a quad tree: a solid-color block is one leaf, a mixed block splits into four quadrants and recurses. Adapted for verification: the tree comes back as a flat preorder list of [value, isLeaf] pairs rather than a live node object.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A square grid of 0s and 1s arrives, with its side length always a power of two, and the task is to compress it into a quad tree: a block that is entirely one color becomes a single leaf, while a block mixing both colors splits into its four equal quadrants and each quadrant gets the same treatment recursively.

This site verifies the result differently than a live tree object would: the answer comes back as a flat list of [value, isLeaf] pairs written in preorder, one pair per node the recursion actually visits.

A leaf's value reflects the single color filling its whole block, while an internal (non-leaf) node's value can be treated as a placeholder, since what matters there is only that it isn't a leaf and its four children follow next in the preorder listing.

EX 01

grid = [[0]]

→ [[0, 1]]

SINGLE CELL, OFF

EX 02

grid = [[1]]

→ [[1, 1]]

SINGLE CELL, ON

EX 03

grid = [[1, 1], [1, 1]]

→ [[1, 1]]

2X2 UNIFORM ON

the grid's side length is always a power of two
every cell holds exactly 0 or 1, nothing else
a uniform block becomes one leaf; anything else splits into four quadrants
the answer is the preorder [value, isLeaf] listing of every node visited

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Every recursive call answers one question first: is this whole block a single color? If yes, you're done — no need to look deeper.

HINT 2 THE STRUCTURE

When it's not uniform, the block always splits into four equal quadrants (grid side is a power of two), and each quadrant is the exact same subproblem at half the size.

HINT 3 ONE STEP FROM THE ANSWER

Re-scanning a block to check uniformity costs you its full area every single call. A 2-D prefix-sum array turns that scan into two subtractions — uniform means the block sum is 0 or size².

COACH'S BOARD — THE PATTERN, STEP BY STEP

FOUR QUADRANTS, ONE PASSPATTERN · PREFIX SUM CHECKgrid = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]

STEP 1

The whole 4x4 block mixes 0s and 1s — not uniform, so it must split into four 2x2 quadrants and recurse.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/construct-quad-tree.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def construct(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        prefix = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n):
            for j in range(n):
                prefix[i + 1][j + 1] = grid[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j]

        def region_sum(r: int, c: int, size: int) -> int:
            return prefix[r + size][c + size] - prefix[r][c + size] - prefix[r + size][c] + prefix[r][c]

        result: List[List[int]] = []

        def build(r: int, c: int, size: int) -> None:
            total = region_sum(r, c, size)
            if total == 0:
                result.append([0, 1])
                return
            if total == size * size:
                result.append([1, 1])
                return
            result.append([0, 0])
            half = size // 2
            build(r, c, half)
            build(r, c + half, half)
            build(r + half, c, half)
            build(r + half, c + half, half)

        build(0, 0, n)
        return result

TIME O(N²)SPACE O(N²)PYTHON · RACE PACE · 30 LN

class Solution:
    def construct(self, grid: List[List[int]]) -> List[List[int]]:
        result: List[List[int]] = []

        def is_uniform(r: int, c: int, size: int):
            first = grid[r][c]
            for i in range(r, r + size):
                for j in range(c, c + size):
                    if grid[i][j] != first:
                        return False, first
            return True, first

        def build(r: int, c: int, size: int) -> None:
            uniform, val = is_uniform(r, c, size)
            if uniform:
                result.append([val, 1])
                return
            result.append([0, 0])
            half = size // 2
            build(r, c, half)
            build(r, c + half, half)
            build(r + half, c, half)
            build(r + half, c + half, half)

        build(0, 0, len(grid))
        return result

TIME O(N²·LOG N)SPACE O(N²)PYTHON · TRAINING PACE · 26 LN

class Solution {
    private int[][] prefix;

    public int[][] construct(int[][] grid) {
        int n = grid.length;
        prefix = new int[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                prefix[i + 1][j + 1] = grid[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
            }
        }
        List<int[]> result = new ArrayList<>();
        build(0, 0, n, result);
        return result.toArray(new int[0][]);
    }

    private int regionSum(int r, int c, int size) {
        return prefix[r + size][c + size] - prefix[r][c + size] - prefix[r + size][c] + prefix[r][c];
    }

    private void build(int r, int c, int size, List<int[]> result) {
        int total = regionSum(r, c, size);
        if (total == 0) {
            result.add(new int[] { 0, 1 });
            return;
        }
        if (total == size * size) {
            result.add(new int[] { 1, 1 });
            return;
        }
        result.add(new int[] { 0, 0 });
        int half = size / 2;
        build(r, c, half, result);
        build(r, c + half, half, result);
        build(r + half, c, half, result);
        build(r + half, c + half, half, result);
    }
}

TIME O(N²)SPACE O(N²)JAVA · RACE PACE · 38 LN

class Solution {
    private int[][] grid;

    public int[][] construct(int[][] grid) {
        this.grid = grid;
        List<int[]> result = new ArrayList<>();
        build(0, 0, grid.length, result);
        return result.toArray(new int[0][]);
    }

    private void build(int r, int c, int size, List<int[]> result) {
        int first = grid[r][c];
        boolean uniform = true;
        outer:
        for (int i = r; i < r + size; i++) {
            for (int j = c; j < c + size; j++) {
                if (grid[i][j] != first) {
                    uniform = false;
                    break outer;
                }
            }
        }
        if (uniform) {
            result.add(new int[] { first, 1 });
            return;
        }
        result.add(new int[] { 0, 0 });
        int half = size / 2;
        build(r, c, half, result);
        build(r, c + half, half, result);
        build(r + half, c, half, result);
        build(r + half, c + half, half, result);
    }
}

TIME O(N²·LOG N)SPACE O(N²)JAVA · TRAINING PACE · 34 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED