LESSON 254 OF 338 · DIVIDE AND CONQUER

Z Pattern in Go: Recursive Quadrant Fill

Practice O(n²) Read the full explanation

Given an integer N, which is a power of 2, return a square of length N filled with the numbers {1, 2, 3, ... N²} followig the "Z Pattern".

This consists of recursively traversing the 4 quadrants in the order: upper-left, upper-right, lower-left, lower-right.

Example 1:

Input: N = 2
Output: [
    [1, 2], 
    [3, 4]
]

Example 2:

Input: N = 4
Output:[
    [1,   2,  5,  6],
    [3,   4,  7,  8],
    [9,  10, 13, 14]
    [11, 12, 15, 16]
]

STEP 1 OF 11

Guided

Ctrl + Enter to check

GO · DIVIDE AND CONQUER

Z Pattern in Go, explained

Problem overview

The function zPattern(n) takes an int n that is a power of 2 and returns an n by n grid, as a [][]int, holding the numbers 1 to n*n. The numbers are placed by splitting the grid into four quadrants and visiting them in this order: upper-left, upper-right, lower-left, lower-right. Inside each quadrant the same rule applies again, down to single cells.

For n = 2 the quadrants are single cells, so the grid is:

[1 2]
[3 4]

For n = 4 each quadrant is a 2 by 2 block filled the same way, and the blocks hold 1-4, 5-8, 9-12 and 13-16 in Z order:

[1 2 5 6]
[3 4 7 8]
[9 10 13 14]
[11 12 15 16]

Approach: fill a square by filling its four quadrants

The pattern is defined recursively, so the code can be too. Filling a square of side length that starts at some corner and uses numbers beginning at firstVal breaks down into four smaller jobs of the same kind:

The upper-left quadrant starts at the same corner with the same firstVal.
The upper-right quadrant starts half a side to the right. It comes second, so its numbers begin after the first quadrant's numbers.
The lower-left quadrant starts half a side down, and two quadrants come before it.
The lower-right quadrant moves down and right, and three quadrants come before it.

A quadrant of side newLen holds newLen * newLen numbers. That gives the offsets 0, 1, 2 and 3 times newLen * newLen for the four first values. The recursion stops at a 1 by 1 square, where the one cell receives firstVal.

Step by step

Allocate the grid. make([][]int, n) creates only the outer slice, whose rows are all nil. A loop with range then gives each row its own make([]int, n), filled with zeros.
Start the fill for the whole grid with a helper, fill(grid, row, col, length, firstVal). The corner is (0, 0), the side is n, and the first number is 1.
Return grid. The helper wrote into it in place.
Declare fill below zPattern, with no result. It writes into the caller's grid, so it has nothing to return.
Base case. When length is 1, store firstVal in grid[row][col].
Recursive case. In the else branch, compute newLen as half of length.
Upper-left. Same row and col, same firstVal.
Upper-right. Same row, column col + newLen, first value firstVal + newLen * newLen.
Lower-left. Row row + newLen, same col, first value firstVal + 2 * newLen * newLen.
Lower-right. Row row + newLen, column col + newLen, first value firstVal + 3 * newLen * newLen.

The solution in Go

func zPattern(n int) [][]int {
    grid := make([][]int, n)
    for i := range grid {
        grid[i] = make([]int, n)
    }
    fill(grid, 0, 0, n, 1)
    return grid
}
func fill(grid [][]int, row int, col int, length int, firstVal int) {
    if length == 1 {
        grid[row][col] = firstVal
    } else {
        newLen := length / 2
        fill(grid, row, col, newLen, firstVal)
        fill(grid, row, col+newLen, newLen, firstVal+newLen*newLen)
        fill(grid, row+newLen, col, newLen, firstVal+2*newLen*newLen)
        fill(grid, row+newLen, col+newLen, newLen, firstVal+3*newLen*newLen)
    }
}

Go details worth knowing:

A 2D slice is a slice of slices. There is no single block of memory with rows and columns. Each row is its own slice, which is why every row needs its own make. Writing to a row before that would panic, because a nil slice has length 0.
Slices are passed by value, but they share their data. The grid parameter is a copy of the slice header, which holds a pointer to the same rows. Writes such as grid[row][col] = firstVal are therefore visible to the caller. That is why fill returns nothing.
for i := range grid gives only the index when you ask for one variable. That is all this loop needs.
Parameter lists. The helper repeats int for each parameter. Go would also accept row, col, length, firstVal int.
Order of the calls. The four calls write to separate quadrants, so each one only needs the right corner and first number. The calls could run in any order and the grid would be the same.

Complexity

Time: O(n²). Every call that doesn't hit the base case makes four calls on squares of half the side, and the base cases are the n*n cells, each written once. The total number of calls is about 4/3 of n*n, still O(n²).

Space: O(n²) for the grid itself, which the answer requires. The recursion adds only O(log n) for the call stack, since each level halves the side.

Edge cases and common mistakes

n = 1. The first call is the base case, and the result is [[1]].
n not a power of 2. With n = 3, length / 2 truncates to 1 and the quadrants no longer cover the grid, so the pattern is wrong. The size must be a power of 2, as the problem promises.
n = 0. Half of 0 is 0, so fill would call itself with the same arguments forever until Go stops the program with a stack overflow. This input isn't a power of 2, so it doesn't occur.
Forgetting to allocate the rows. Skipping the range loop gives an index-out-of-range panic on the first write.
Wrong offsets. Using newLen instead of newLen * newLen for the first values would number the quadrants by their side, not by how many cells they hold.
Confusing row and column. The upper-right quadrant changes only the column and the lower-left changes only the row.

Testing

For n = 1 the result is [[1]]. For n = 2 it is [[1 2] [3 4]]. For n = 8 the first row is 1 2 5 6 17 18 21 22 and the last row is 43 44 47 48 59 60 63 64.

Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free