Start learning free

LESSON 284 OF 414 · DIVIDE AND CONQUER

Z Pattern in Scala: 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} 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

    SCALA · DIVIDE AND CONQUER

    Z Pattern in Scala, explained

    Problem overview

    The method zPattern receives an integer n, a power of 2, and returns an n by n grid, an Array[Array[Int]], filled with 1, 2, ..., n² in "Z order". The grid is split into four quadrants, which are visited as upper-left, upper-right, lower-left, lower-right. Each quadrant is then 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. The upper-left block holds 1 to 4, the upper-right 5 to 8, the lower-left 9 to 12 and the lower-right 13 to 16:

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

    Approach: every quadrant is a smaller copy of the problem

    Inside the 4 by 4 grid, the upper-left quadrant is exactly the 2 by 2 answer, and so are the other three, except that their numbers start at a different value. So a recursive function only has to know where a square sits and which number it starts with:

    • its top-left corner, row and col;
    • its side length, len;
    • its first number, firstVal.

    A square of side len holds len * len numbers. Each of its four quadrants has side newLen = len / 2 and holds newLen * newLen numbers, so the quadrants start at firstVal, firstVal + newLen * newLen, firstVal + 2 * newLen * newLen and firstVal + 3 * newLen * newLen. A 1 by 1 square is the base case: it holds just firstVal.

    Because the power-of-2 side halves exactly each time, the recursion reaches side 1 on every branch, never a side that doesn't divide evenly.

    Step by step

    1. Create the grid with Array.fill(n)(Array.ofDim[Int](n)): n rows, each an Array[Int] of n zeros. The second argument of fill is evaluated once per row, so every row is a separate array.
    2. Call the helper on the whole grid: corner (0, 0), side n, first value 1.
    3. Return the grid. The helper wrote into it in place.
    4. Declare fill with the grid, row, col, len and firstVal, returning Unit. It returns nothing because it modifies the caller's arrays.
    5. Handle the 1 by 1 case. If len == 1, set grid(row)(col) = firstVal.
    6. Otherwise split. In the else branch compute newLen, half the side.
    7. Upper-left: same corner, first value firstVal.
    8. Upper-right: the column moves right by newLen, and the numbers start after the upper-left block.
    9. Lower-left: the row moves down by newLen, with two blocks of numbers before it.
    10. Lower-right: both move by newLen, with three blocks before it.

    The solution in Scala

    class Solution {
    def fill(grid: Array[Array[Int]], row: Int, col: Int, len: Int, firstVal: Int): Unit = {
        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)
        }
    }

    def zPattern(n: Int): Array[Array[Int]] = {
        val grid = Array.fill(n)(Array.ofDim[Int](n))
        fill(grid, 0, 0, n, 1)
        return grid
    }
}

    Scala details:

    • grid(row)(col). Scala indexes arrays with parentheses. grid(row) is a row, and the second pair of parentheses picks the cell in it. Assigning to it, grid(row)(col) = firstVal, updates the array.
    • Arrays are mutable and shared. fill receives a reference to the same grid, so what it writes is visible in zPattern. That is why it can return Unit.
    • if / else as the body. Both branches have type Unit, so the method needs no return. The final return grid in zPattern is optional in Scala: writing just grid as the last line does the same.
    • The shared-row trap. Building the rows from one array that you created beforehand is a bug. With val row = Array.ofDim[Int](2) and Array.fill(2)(row), both rows are the same array, and after shared(0)(0) = 9 printing the rows gives 9,0 | 9,0. Creating the array inside the second argument, as the lesson does, gives 9,0 | 0,0.

    Complexity

    Time: O(n²). Every cell is written exactly once. The recursion makes n² calls that write a cell, plus (n² - 1) / 3 calls that only split a square, so the total is (4n² - 1) / 3 calls, each doing constant work.

    Space: O(n²). The result itself has n² cells. The recursion adds only O(log n), since each level halves the side and there are log2(n) + 1 levels.

    Edge cases and common mistakes

    • n = 1. The first call hits the base case, and the result is [[1]].
    • Using the wrong offsets. Mixing up the lower-left and upper-right quadrant produces a grid that fills column-first. The upper-right quadrant gets one block of numbers before it and the lower-left gets two.
    • A side that isn't a power of 2. For n = 3, len / 2 is 1, so the four quadrants are single cells that cover only the 2 by 2 corner. The result is 1 2 0 / 3 4 0 / 0 0 0: the rest of the grid stays 0. The requirement that n be a power of 2 is what keeps the split exact.
    • n = 0. The base case tests len == 1, which 0 never reaches. Half of 0 is 0, so the function calls itself forever and the program fails with a StackOverflowError.
    • Forgetting the first value. The quadrants must start at firstVal + k * newLen * newLen, not at a global counter that restarts from 1.

    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]].
    • For n = 8 the last row is 43 44 47 48 59 60 63 64.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free