Start learning free

LESSON 260 OF 348 · DIVIDE AND CONQUER

Z Pattern in Kotlin: Divide and Conquer on a 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} 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

    KOTLIN · DIVIDE AND CONQUER

    Z Pattern in Kotlin, explained

    Problem overview

    Given a number n that is a power of 2, zPattern returns an n by n grid filled with the numbers 1 to n² in a "Z" order. The order is defined recursively. Split the square into four equal quadrants and fill them in this order: upper-left, upper-right, lower-left, lower-right. Inside each quadrant, repeat the same rule, until you reach single cells.

    For n = 2 every quadrant is one cell, so the grid is just the Z itself:

    1 2
3 4

    For n = 4 each quadrant is a 2 by 2 square that is filled like the grid above. 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:

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

    Notice that the numbers inside each quadrant are consecutive. That is the fact the whole solution rests on.

    Approach

    A square of side len holds len * len numbers. If we know the top-left corner of the square and the first number to write in it, we can describe the work for the whole square with four smaller jobs of exactly the same kind:

    • the upper-left quadrant starts at the same corner and gets the first number;
    • the upper-right quadrant starts half a side to the right and gets the first number plus the size of one quadrant;
    • the lower-left quadrant starts half a side down and gets the first number plus two quadrant sizes;
    • the lower-right quadrant moves down and right and gets the first number plus three quadrant sizes.

    When the side is 1, the square is a single cell and we write the first number there. This is divide and conquer: the problem is split into four independent pieces of half the side, and no step has to combine results afterwards, because every piece writes straight into the shared grid.

    Because n is a power of 2, halving always gives a whole number, all the way down to 1.

    Step by step

    1. Create the grid. In zPattern, Array(n) { IntArray(n) } builds n rows. The lambda runs once per row, so each row is its own IntArray of n zeros.
    2. Delegate to a helper. The helper fill(grid, row, col, len, firstVal) fills one square. The first call covers the entire grid: corner (0, 0), side n, first value 1.
    3. Return the grid. The helper changed the array in place, so there is nothing to collect.
    4. Declare fill. It takes the grid, the corner as row and col, the side len and firstVal. It has no return type, which means it returns Unit: its job is the side effect on the grid.
    5. Base case. If len == 1, write firstVal into grid[row][col]. This stops the recursion.
    6. Recursive case. Compute newLen = len / 2, the side of each quadrant.
    7. Four calls, in Z order. The row and column offsets are 0 or newLen, and the first values grow by newLen * newLen for every quadrant already filled.

    The solution in Kotlin

    class Solution {
    fun fill(grid: Array<IntArray>, row: Int, col: Int, len: Int, firstVal: Int) {
        if (len == 1) {
            grid[row][col] = firstVal
        } else {
            val newLen = len / 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)
        }
    }

    fun zPattern(n: Int): Array<IntArray> {
        val grid = Array(n) { IntArray(n) }
        fill(grid, 0, 0, n, 1)
        return grid
    }
}

    A few Kotlin details:

    • Arrays are references. fill receives the same Array<IntArray> object that zPattern created, so writing grid[row][col] inside the helper is visible to the caller. That is why fill needs no return value.
    • Array(n) { IntArray(n) } is safe. The lambda creates a new row for each index. Reusing a single IntArray for every row would make all the rows the same object.
    • val newLen inside else. The value never changes after it is computed, so val is the right choice. len / 2 is integer division, exact here because len is even whenever it is bigger than 1.
    • Printing the result. println(grid) shows only an object reference. To see the numbers, print each row, for example for (r in grid) println(r.joinToString(" ")), or use grid.contentDeepToString().

    Complexity

    Time. Every call either writes one cell or makes four calls on squares with a quarter of the cells. The recursion ends in exactly n * n single-cell calls, and the calls above them add up to about a third more, so the total work is O(n²). The output has n² numbers, so no solution can do better.

    Space. The grid itself takes O(n²). On top of it the recursion goes only log₂(n) levels deep, because the side halves at every level, so the call stack adds O(log n).

    Edge cases and common mistakes

    • n = 1. The first call already hits the base case, and the result is a grid holding just 1.
    • Values that are not powers of 2. The lesson guarantees a power of 2. With n = 3, len / 2 is 1 and the four quadrants cover only a 2 by 2 corner, leaving the rest of the grid at 0. Do not rely on the code for such inputs.
    • Forgetting the offsets. If the upper-right call uses col instead of col + newLen, the quadrants overwrite each other.
    • Wrong first values. Each quadrant must start after all the cells of the previous ones, so the multipliers are 0, 1, 2 and 3 times newLen * newLen. Using len there instead of newLen skips numbers.
    • Swapping row and column. Row is the vertical position. The upper-right quadrant changes the column, and the lower-left changes the row.

    Testing

    Try these in the editor above:

    • zPattern(1) gives [[1]].
    • zPattern(2) gives [[1, 2], [3, 4]].
    • zPattern(4) ends with the row [11, 12, 15, 16], and its first row is [1, 2, 5, 6].
    • For zPattern(8), the upper-right quadrant starts with 17 and the lower-left with 33.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free