Start learning free

LESSON 285 OF 415 · DIVIDE AND CONQUER

Z Pattern in Swift: Recursive Quadrants on a Square Grid

Practice O(n2) 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, ... n2} following 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
    Ctrl + Enter to check

    SWIFT · DIVIDE AND CONQUER

    Z Pattern in Swift, explained

    Problem overview

    The method zPattern receives an integer n, a power of 2, and returns an n by n grid ([[Int]]) holding the numbers 1 to n * n in "Z" order. The grid is split into four quadrants, visited as upper-left, upper-right, lower-left, lower-right. Each quadrant is filled the same way, recursively, 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, and the blocks take the numbers 1 to 4, 5 to 8, 9 to 12 and 13 to 16 in that order:

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

    Approach: fill a square from its top-left corner

    The key observation is that a square of side length contains length * length cells, and those cells get a block of consecutive numbers. If you know the corner of the square and the first number it receives, the four quadrants follow directly:

    • the upper-left quadrant starts at the same corner with the same first number;
    • the upper-right quadrant starts newLength columns to the right, after the newLength * newLength numbers of the first quadrant;
    • the lower-left quadrant starts newLength rows down, after two quadrants;
    • the lower-right quadrant moves both ways, after three quadrants.

    Here newLength is half of length. Since n is a power of 2, halving gives a whole number until the side is 1. A 1 by 1 square holds one number, which stops the recursion.

    Take n = 4. The call fill(&grid, 0, 0, 4, 1) has newLength = 2. The upper-right quadrant starts at column 2 with first value 1 + 2 * 2 = 5. The lower-left quadrant starts at row 2 with first value 1 + 2 * 4 = 9, and the lower-right at row 2, column 2 with first value 1 + 3 * 4 = 13. This matches the grid above.

    Step by step

    1. Create the grid in zPattern as n rows of n zeros. It is a var, since the helper changes it.
    2. Call the helper fill once for the whole grid: corner (0, 0), side n, first value 1. The grid goes in as &grid because the parameter is inout.
    3. Return grid. By then the helper has filled it in place.
    4. Declare fill with the grid, a row, a column, a length and a firstValue, none labeled and no return value.
    5. Base case: when length is 1, store firstValue in grid[row][column].
    6. Otherwise, split. Compute newLength as half of length.
    7. Recurse on the four quadrants in Z order, using the corners and first values described above.

    The solution in Swift

    class Solution {
    func zPattern(_ n: Int) -> [[Int]] {
        var grid = Array(repeating: Array(repeating: 0, count: n), count: n)
        fill(&grid, 0, 0, n, 1)
        return grid
    }

    func fill(_ grid: inout [[Int]], _ row: Int, _ column: Int, _ length: Int, _ firstValue: Int) {
        if length == 1 {
            grid[row][column] = firstValue
        } else {
            let newLength = length / 2
            fill(&grid, row, column, newLength, firstValue)
            fill(&grid, row, column + newLength, newLength, firstValue + newLength * newLength)
            fill(&grid, row + newLength, column, newLength, firstValue + 2 * newLength * newLength)
            fill(&grid, row + newLength, column + newLength, newLength, firstValue + 3 * newLength * newLength)
        }
    }
}

    The Swift details worth a closer look:

    • inout and &. Swift function parameters are constants. Marking one inout lets the function change the caller's variable, and the caller must show it by writing &grid. Leaving the & out is a compile error: passing value of type '[[Int]]' to an inout parameter requires explicit '&'.
    • Why var grid. An inout argument has to be a variable. A grid declared with let can't be passed with &.
    • Nested repeating arrays. Array(repeating: Array(repeating: 0, count: n), count: n) builds the inner row once and repeats it. Arrays are value types, so the rows are independent: writing to grid[1][0] doesn't touch any other row. This differs from a grid of reference objects, where the same object would be shared.
    • Two-step subscripts. grid[row][column] = firstValue writes straight into the stored row. No copy of the row is made.
    • Calling a method declared later. Inside a class, zPattern can call fill even though fill is written below it. Order of methods doesn't matter in a Swift type.
    • Return type. Because fill has no ->, it returns nothing, and its result is the change it makes to the grid.

    Complexity

    Time: O(n²). Every call with length > 1 makes four calls with a quarter of the area, and the recursion ends at single cells. There are n * n of those, one per number written, and the calls above them add up to about a third more, so the total work is proportional to the number of cells. Creating the grid also costs O(n²).

    Space: O(n²). The returned grid has n * n cells. The recursion adds only O(log n) stack frames, since the side halves at each level, so the grid dominates.

    Edge cases and common mistakes

    • n = 1. The first call is already the base case, and the result is [[1]].
    • Quadrant order. Swapping the lower-left and upper-right calls produces a different pattern. The first values firstValue + newLength * newLength and firstValue + 2 * newLength * newLength must match the visiting order.
    • Offsets in the wrong direction. The upper-right quadrant moves only the column, and the lower-left quadrant only the row. Moving both for either of them places numbers on the wrong diagonal.
    • Using n instead of length. Inside fill, the side that matters is the current square's length, which shrinks with each level.
    • Input that isn't a power of 2. The statement guarantees a power of 2. For other values the halves aren't exact, and for n = 0 the length never reaches 1, so the recursion doesn't end and the program crashes with a stack overflow.

    Testing

    • n = 1 gives [[1]].
    • n = 2 gives [[1, 2], [3, 4]].
    • n = 4 gives [[1, 2, 5, 6], [3, 4, 7, 8], [9, 10, 13, 14], [11, 12, 15, 16]].
    • n = 8 gives a first row of [1, 2, 5, 6, 17, 18, 21, 22] and a last row of [43, 44, 47, 48, 59, 60, 63, 64].
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free