Problem overview
The method zPattern receives an integer n, a power of 2, and returns an n by n grid (a list of n lists) holding the numbers 1 to n * n. The numbers are placed by tracing a "Z" at every scale: split the square into four quadrants and visit them in the order upper-left, upper-right, lower-left, lower-right. Inside each quadrant, repeat the same rule.
For n = 2 each quadrant is a single cell, so the grid is read like text, left to right and top to bottom:
[1, 2]
[3, 4]
For n = 4 the four 2 by 2 quadrants get the numbers 1 to 4, 5 to 8, 9 to 12 and 13 to 16 in Z order, and each quadrant is itself filled in a Z:
[1, 2, 5, 6]
[3, 4, 7, 8]
[9, 10, 13, 14]
[11, 12, 15, 16]
Approach: fill each quadrant recursively
Every quadrant is a smaller version of the whole problem, which is the signature of divide and conquer. To fill a square of side len whose top-left corner is at (row, col), starting from the number firstVal:
- If the square is 1 by 1, put
firstValin that cell. This is the base case. - Otherwise cut the side in half,
newLen = len // 2, and fill four squares of that side.
The only thing to work out is where each quadrant starts and which number it begins with. Each quadrant holds newLen * newLen cells, and the quadrants are visited one after another, so the quadrant in position 0, 1, 2 or 3 of the Z order starts at firstVal plus 0, 1, 2 or 3 times that count:
| Quadrant | Top-left corner | First value |
|---|---|---|
| Upper-left | (row, col) | firstVal |
| Upper-right | (row, col + newLen) | firstVal + newLen * newLen |
| Lower-left | (row + newLen, col) | firstVal + 2 * newLen * newLen |
| Lower-right | (row + newLen, col + newLen) | firstVal + 3 * newLen * newLen |
Because n is a power of 2, halving always gives a whole number, down to side 1.
Here is the call tree for n = 4. The first call has side 4 and splits into four calls of side 2, with first values 1, 5, 9 and 13. The second call, at corner (0, 2) with first value 5, splits again into four calls of side 1 that write 5, 6, 7 and 8 into (0, 2), (0, 3), (1, 2) and (1, 3). The other three side-2 calls do the same in their own corners.
Step by step
- Create the grid in
zPatternwith a nested list comprehension: one comprehension builds a row ofnzeros, and the outer one buildsnseparate rows. Every cell is overwritten later, so the zeros are placeholders. - Call the helper once for the whole grid: top-left corner
0, 0, siden, first value1. The helper is a method of the class, so the call goes throughself. - Return
grid. The helper wrote into it in place, so it already holds the answer. - Write
fillwith the parametersself, grid, row, col, len, firstVal. It returns nothing. - Handle the base case: when
len == 1, setgrid[row][col] = firstVal. - In the
elsebranch, computenewLen = len // 2. - Make four recursive calls, one per quadrant, in Z order, using the table above.
The solution in Python
class Solution:
def fill(self, grid, row, col, len, firstVal):
if len == 1:
grid[row][col] = firstVal
else:
newLen = len // 2
self.fill(grid, row, col, newLen, firstVal)
self.fill(grid, row, col + newLen, newLen, firstVal + newLen * newLen)
self.fill(grid, row + newLen, col, newLen, firstVal + 2 * newLen * newLen)
self.fill(grid, row + newLen, col + newLen, newLen, firstVal + 3 * newLen * newLen)
def zPattern(self, n: int) -> List[List[int]]:
grid = [[0 for i in range(n)] for j in range(n)]
self.fill(grid, 0, 0, n, 1)
return grid
Python details that matter here:
- The parameter named
lenhides the built-inlen()insidefill. The method never needs the built-in, so it works, but a name likesizewould be safer. //is integer division./would give a float such as2.0, and a float cannot be used as a list index.- Build the rows separately. Writing
[[0] * n] * nrepeats a reference to one row, so setting one cell changes the same column in every row. The comprehension creates a new list per row. - The helper changes the grid in place. Lists are passed by reference, so no return value is needed.
Complexity
Each call either writes one cell or makes four calls on a quarter of the area. The leaves of the recursion are the n * n cells, and the whole tree has (4 * n * n - 1) / 3 calls: 21 for n = 4 and 85 for n = 8. The time is O(n²), which is optimal because the output itself has n² cells. The grid takes O(n²) space, and the recursion adds only O(log n) stack frames, since the side halves at each level. Even for n = 1024 the depth is just 10.
Edge cases and common mistakes
n = 1. The base case fires immediately and the result is[[1]].- Wrong order of quadrants. Swapping the lower-left and upper-right calls gives a transposed Z, which is a different grid. The offsets 1, 2 and 3 times
newLen * newLenmust match the order of the calls. - Forgetting to move the corner. Upper-right changes only the column and lower-left changes only the row; lower-right changes both.
- Input that is not a power of 2. For
n = 3the halving gives3 // 2 = 1, the quadrants no longer cover the grid, and the result is[[1, 2, 0], [3, 4, 0], [0, 0, 0]]. Forn = 0the side never reaches 1 and the recursion ends in aRecursionError. The problem only promises powers of 2.
Testing
zPattern(1)returns[[1]].zPattern(2)returns[[1, 2], [3, 4]].zPattern(4)returns[[1, 2, 5, 6], [3, 4, 7, 8], [9, 10, 13, 14], [11, 12, 15, 16]].- For
zPattern(8)the first row is[1, 2, 5, 6, 17, 18, 21, 22]and the bottom-right cell is 64.
