Start learning free

LESSON 259 OF 347 · DIVIDE AND CONQUER

Z Pattern in C#: Divide and Conquer on a 2D Array

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

    C# · DIVIDE AND CONQUER

    Z Pattern in C#, explained

    Problem overview

    ZPattern(int n) receives n, a power of 2, and returns an n by n grid filled with the numbers 1 to n * n in a "Z" order. The order is defined recursively: split the square into four quadrants, visit them as upper-left, upper-right, lower-left, lower-right, and fill each quadrant the same way.

    For n = 2 there is nothing smaller to split into, and the rows are 1 2 and 3 4. For n = 4 the grid is:

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

    The upper-left 2 by 2 quadrant holds 1 to 4, the upper-right holds 5 to 8, the lower-left holds 9 to 12, and the lower-right holds 13 to 16. Inside each quadrant, the cells follow the same Z.

    Approach: fill squares by recursion

    The key observation is that a square of side len is the same problem as the whole grid, just placed somewhere else and starting from a different number. So the helper Fill(grid, row, col, len, firstVal) fills the len by len square whose top-left corner is at (row, col) with consecutive numbers starting at firstVal.

    • Base case: a 1 by 1 square is a single cell. Put firstVal there.
    • Recursive case: split into four quadrants of side newLen = len / 2. Each quadrant holds newLen * newLen numbers, so the quadrants start at firstVal, firstVal + newLen * newLen, firstVal + 2 * newLen * newLen and firstVal + 3 * newLen * newLen.

    Only the corner moves between quadrants. The upper-right one shifts the column by newLen, the lower-left shifts the row, and the lower-right shifts both.

    For n = 4, Fill(grid, 0, 0, 4, 1) has newLen = 2 and starts the four quadrants at 1, 5, 9 and 13, with corners (0, 0), (0, 2), (2, 0) and (2, 2). The upper-right call, Fill(grid, 0, 2, 2, 5), splits again into four single cells, which get 5, 6, 7 and 8. This yields the rows 5 6 and 7 8.

    Step by step

    1. Create the grid in ZPattern with new int[n, n], as an int[,] named grid. Its cells start at 0, and the helper overwrites each of them.
    2. Call the helper once on the whole grid: Fill(grid, 0, 0, n, 1). The whole grid is one big square starting at the corner, with first value 1.
    3. Return grid. The helper filled it in place.
    4. Declare the helper above ZPattern as public void Fill with parameters int[,] grid, int row, int col, int len and int firstVal. It returns nothing, because arrays are reference types: the helper writes into the caller's grid.
    5. Base case. If len == 1, set grid[row, col] = firstVal.
    6. Otherwise, in the else branch, compute newLen = len / 2.
    7. Fill the upper-left quadrant at the same row and col, starting at firstVal.
    8. Fill the upper-right quadrant at column col + newLen, starting at firstVal + newLen * newLen.
    9. Fill the lower-left quadrant at row row + newLen, starting at firstVal + 2 * newLen * newLen.
    10. Fill the lower-right quadrant at row row + newLen and column col + newLen, starting at firstVal + 3 * newLen * newLen.

    The solution in C#

    class Solution {
    public void Fill(int[,] grid, int row, int col, int len, int firstVal) {
        if (len == 1) {
            grid[row, col] = firstVal;
        } else {
            int 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);
        }
    }

    public int[,] ZPattern(int n) {
        int[,] grid = new int[n, n];
        Fill(grid, 0, 0, n, 1);
        return grid;
    }
}

    C# details worth knowing

    • Rectangular arrays. int[,] is a single block of n * n cells, indexed with one pair of brackets and a comma: grid[row, col]. This differs from a jagged array int[][], which is indexed as grid[row][col] and whose rows are separate arrays. The two are different types and don't mix.
    • Dimensions. grid.GetLength(0) is the number of rows and grid.GetLength(1) the number of columns. The Length property of an int[,] is the total cell count, n * n here, not the side.
    • A shared grid. Arrays are reference types, so every recursive call receives a reference to the same grid. That is why Fill can return void.
    • No overflow worries here. The largest value is n * n, which fits an int for any n a grid could reasonably have.

    Complexity

    Every call either writes one cell or makes four calls on squares a quarter of the area. The recursion tree has n * n leaves, one per cell, and the internal nodes number about a third as many. Each does constant work, so the time is O(n²), which is also the size of the output.

    The recursion goes log₂ n levels deep, but the grid itself takes n² cells, so the total space is O(n²). Without the output, the extra space is only the O(log n) call stack.

    Edge cases and common mistakes

    • n = 1. The grid has one cell, and the base case writes 1 into it right away.
    • A size that is not a power of 2. The method relies on exact halving. With n = 3, len / 2 is 1, so only the top-left 2 by 2 block gets filled and the other cells stay 0. The lesson guarantees powers of 2, so there is no check.
    • Wrong first values. Each quadrant must start after all the numbers of the quadrants before it. A quadrant holds newLen * newLen numbers, not newLen, so adding only newLen would make the quadrants overlap in value.
    • Swapping the row and column shifts. The upper-right quadrant moves the column, not the row. Mixing them up visits the quadrants in the wrong order, so the numbers land in the wrong places.
    • Mixing up the index syntax. grid[row][col] doesn't compile on an int[,]. Use grid[row, col].

    Testing

    For n = 1 the grid is the single value 1. For n = 2, the rows are 1 2 and 3 4. For n = 4, the grid is the one drawn above, and its last row is 11 12 15 16.

    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free