Start learning free

LESSON 260 OF 348 · DIVIDE AND CONQUER

Z Pattern in TypeScript: Recursive Quadrant Fill

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} 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
    Ctrl + Enter to check

    TYPESCRIPT · DIVIDE AND CONQUER

    Z Pattern in TypeScript, explained

    Problem overview

    The method zPattern receives n, a power of 2, and returns an n by n grid holding the numbers 1 to n * n. The numbers follow a "Z" order: split the square into four quadrants, visit them as upper-left, upper-right, lower-left, lower-right, and apply the same rule inside every quadrant until a quadrant is a single cell.

    For n = 2 each quadrant is one cell, so the result is [[1, 2], [3, 4]]. For n = 4 the upper-left quadrant takes 1 to 4, the upper-right takes 5 to 8, the lower-left takes 9 to 12 and the lower-right takes 13 to 16, and inside each quadrant the same Z repeats:

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

    Approach: let a helper fill one square

    Computing the number for a given cell directly means thinking about bits of the row and column. The recursive view is simpler. Suppose a helper can fill any square of the grid, given its top-left corner, its side length and the first number to write. A square of side 1 is just one cell: write the first number there. A larger square is four squares of half the side, and the numbers are consecutive in Z order, so each quadrant starts where the previous one ended.

    Each quadrant of side newLen holds newLen * newLen numbers. That gives the four starting values:

    • upper-left: firstVal;
    • upper-right: firstVal + newLen * newLen;
    • lower-left: firstVal + 2 * newLen * newLen;
    • lower-right: firstVal + 3 * newLen * newLen.

    Because n is a power of 2, halving always gives a whole number, and after log2(n) halvings every square has side 1. That is where the recursion stops.

    Step by step

    1. Build the empty grid. new Array(n) makes a row of n empty slots, and a loop puts a separate such array in each of the n positions of grid. Each row must be its own array.
    2. Call this.fill once for the whole grid: corner (0, 0), side n, first value 1. Methods of a class are called through this.
    3. Return grid. The helper wrote into it in place, so there is nothing to copy.
    4. Declare fill with parameters grid, row, col, len and firstVal, returning void.
    5. Handle the base case. When len === 1, store firstVal at grid[row][col].
    6. Add the else branch for every larger square.
    7. Compute the half side, newLen, with Math.floor(len / 2). In TypeScript / is not integer division, so this is how you get a whole number back.
    8. Fill the upper-left quadrant at the same corner, with the same first value.
    9. Fill the upper-right quadrant. Only the column moves, by newLen, and the first value skips one quadrant.
    10. Fill the lower-left quadrant. Only the row moves, and the first value skips two quadrants.
    11. Fill the lower-right quadrant. Both row and column move, and the first value skips three quadrants.

    The solution in TypeScript

    class Solution {
    fill(grid: number[][], row: number, col: number, len: number, firstVal: number): void {
        if (len === 1) {
            grid[row][col] = firstVal;
        } else {
            let newLen: number = Math.floor(len / 2);
            this.fill(grid, row, col, newLen, firstVal);
            this.fill(grid, row, col + newLen, newLen, firstVal + newLen * newLen);
            this.fill(grid, row + newLen, col, newLen, firstVal + 2 * newLen * newLen);
            this.fill(grid, row + newLen, col + newLen, newLen, firstVal + 3 * newLen * newLen);
        }
    }

    zPattern(n: number): number[][] {
        let grid: number[][] = new Array(n);
        for (let i = 0; i < n; i++) {
            grid[i] = new Array(n);
        }
        this.fill(grid, 0, 0, n, 1);
        return grid;
    }
}

    Some TypeScript details worth knowing:

    • Empty slots, not zeros. new Array(3) has length 3 but no elements at all; Node prints it as [ <3 empty items> ]. That is fine here, because fill writes every cell before the grid is returned.
    • Don't build the rows with fill. new Array(2).fill(new Array(2)) puts the same inner array in both positions. After writing sq[0][0] = 1, both rows show the 1. The loop in zPattern creates a new array per row, which avoids that.
    • The type annotation is a promise to the compiler only. number[][] checks the code while compiling, and it is erased in the JavaScript that runs. It does not make the empty slots hold numbers.
    • Passing grid shares it. Arrays are objects, so every recursive call receives a reference to the same grid. That is why fill can return void.
    • Order of arguments. Five parameters of type number are easy to swap, and the compiler cannot notice. Keep row before col.

    Complexity

    Let n be the side of the grid.

    Time: O(n²). Every call with len > 1 makes four calls with half the side, and the calls with len === 1 each write one cell. The grid has n² cells, so there are n² base cases, and the calls above them add up to about a third as many more. The work is proportional to the number of cells.

    Space: O(n²) for the grid that is returned. The recursion itself is only log2(n) levels deep, so the call stack adds O(log n).

    Edge cases and common mistakes

    • n = 1. The base case runs at once and the result is [[1]].
    • Forgetting to move the first value. If all four calls pass firstVal, the quadrants overwrite each other with the same numbers.
    • Using newLen instead of newLen * newLen. A quadrant of side newLen holds newLen * newLen numbers, so the offsets must be multiples of that.
    • Moving the wrong coordinate. The upper-right quadrant is on the same row as the upper-left one, so only col changes. The lower-left changes only row.
    • Not a power of 2. The lesson promises a power of 2. For another size, such as 3, the half side would not be whole, and the recursion would not reach side 1 cleanly.
    • Sharing one row array across all rows, as shown above.

    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 has first row 1 2 5 6 17 18 21 22 and last row 43 44 47 48 59 60 63 64.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free