Understanding the Problem

We are given a square grid of 0s and 1s, and we need to build a Quad-Tree that represents this grid. The idea behind a Quad-Tree is simple: if a region is uniform (all the same value), store it as a single leaf node. If a region has mixed values, split it into four equal quadrants and recurse on each.

Think of it like image compression. If a block of pixels is all the same color, you do not need to store every pixel individually, you just store "this entire block is color X." Only when a block has mixed colors do you need to subdivide further. This recursive subdivision is exactly what a Quad-Tree does.

The key observations are:

The grid size is always a power of 2, which guarantees we can always split evenly into four quadrants.
The recursion bottoms out when either the region is uniform or we reach a single cell (which is trivially uniform).
The four children are always in the order: top-left, top-right, bottom-left, bottom-right.

Key Constraints:

1 <= n <= 64 and n is a power of 2 → The grid is tiny. Even an O(n^2 log n) brute force is at most ~24,576 operations. Performance is not a concern here, so the focus is on correctness and clean recursion.
grid[i][j] is either 0 or 1 → Only two values to deal with. A region is uniform if every cell matches.

Approach 1: Recursive Brute Force

Intuition

The problem description literally gives us the algorithm: check if the region is uniform, and if not, split into four quadrants and recurse. So the brute force approach is a direct translation of the definition.

For any given sub-grid, we scan every cell to see if they are all the same value. If yes, we create a leaf node. If not, we divide the grid into four equal parts and recursively build a Quad-Tree node for each part. The current node becomes an internal node (isLeaf = false) with those four children.

The key detail is getting the coordinates right. We define each sub-grid by its top-left corner (row, col) and its side length. When we subdivide, each child covers a region of half the side length, and the four top-left corners are straightforward to compute.

Algorithm

Define a helper function build(row, col, size) that constructs the Quad-Tree for the sub-grid starting at (row, col) with the given side length.
Scan all cells in the sub-grid to check if every value is the same.
If the sub-grid is uniform, return a leaf node with that value.
Otherwise, compute half = size / 2 and recursively build four children:

Top-left: build(row, col, half)
Top-right: build(row, col + half, half)
Bottom-left: build(row + half, col, half)
Bottom-right: build(row + half, col + half, half)

Return an internal node with isLeaf = false and these four children.

Example Walkthrough

1build(row=0, col=0, size=2): scan entire 2x2 grid for uniformity

scan

1/7

Code

Complexity Analysis

Time Complexity: O(n^2 log n). At each recursion level, all cells are scanned for uniformity. There are log n levels (halving the side each time), and each level touches n^2 cells total.
Space Complexity: O(log n). The recursion depth is at most log n since the grid side halves each time.

The bottleneck is scanning every cell to check uniformity at each recursive level. The same cells get scanned multiple times across recursion levels. What if we could check uniformity in O(1) using a precomputed prefix sum?

Approach 2: Optimized with Prefix Sum

Intuition

The brute force wastes time by scanning sub-grids to check uniformity. But notice what "uniform" really means: either the sum of the sub-grid equals 0 (all zeros) or the sum equals size * size (all ones). If we could compute the sum of any rectangular sub-grid in O(1), we could skip the scanning entirely.

A 2D prefix sum does exactly that. We precompute a matrix where prefix[i][j] holds the sum of all cells in the rectangle from (0,0) to (i-1, j-1). Then, the sum of any sub-rectangle can be computed in O(1) using the inclusion-exclusion principle:

sum(row, col, size) = prefix[row+size][col+size] - prefix[row][col+size] - prefix[row+size][col] + prefix[row][col]

If this sum is 0, the sub-grid is all zeros. If it equals size * size, the sub-grid is all ones. Otherwise, the sub-grid is mixed and needs subdivision.

Why does this work?

The prefix sum gives us a way to compute the sum of any rectangular sub-region in constant time. For a binary grid, the sum tells us everything: if it is 0, every cell is 0. If it equals the area (size * size), every cell is 1. Anything in between means the region is mixed. This replaces the O(size^2) uniformity scan with an O(1) check, which is the only optimization that matters for this problem.

Algorithm

Build a 2D prefix sum array from the grid.
Define a helper function build(row, col, size) that constructs the Quad-Tree for the sub-grid starting at (row, col) with the given side length.
Compute the sum of the sub-grid using the prefix sum in O(1).
If the sum is 0, return a leaf node with val = false.
If the sum equals size * size, return a leaf node with val = true.
Otherwise, compute half = size / 2 and recursively build four children.
Return an internal node with these four children.

Example Walkthrough

1build(0,0,4): regionSum=8, total=16 → 8!=0 and 8!=16, mixed → subdivide

1/6

Code

Complexity Analysis

Time Complexity: O(n^2). Building the prefix sum takes O(n^2). Each recursive call does O(1) work thanks to the prefix sum. The worst case visits O(n^2) nodes.
Space Complexity: O(n^2). The prefix sum array takes O(n^2) space. The recursion depth is O(log n).

Construct Quad Tree

Understanding the Problem

Key Constraints:

Approach 1: Recursive Brute Force

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Optimized with Prefix Sum

Intuition

Algorithm

Example Walkthrough

Code

Get Premium