Problem overview
The function z_pattern receives an i32, n, which is a power of 2, and returns an n by n grid as a Vec<Vec<i32>>. The grid holds the numbers 1 to n * n in a "Z" order. Split the square into four quadrants and number them in the order upper-left, upper-right, lower-left, lower-right. Inside each quadrant, repeat the same rule.
For n = 2 every quadrant is a single cell, so the result is [[1, 2], [3, 4]]. For n = 4 the result is:
[1, 2, 5, 6]
[3, 4, 7, 8]
[9, 10, 13, 14]
[11, 12, 15, 16]
The upper-left 2x2 quadrant gets 1 to 4, the upper-right gets 5 to 8, the lower-left gets 9 to 12 and the lower-right gets 13 to 16. Inside each quadrant the cells follow the same Z.
Approach: fill a square by filling its four quarters
The rule is recursive by its own definition, so the solution is too. A helper, fill_helper, fills one square. It needs to know where the square is and how big it is, and which number goes into its first cell:
rowandcol: the position of the square's top-left corner;len: the side length;first_val: the first number of the square. The square holdslen * lenconsecutive numbers starting there.
If len is 1, the square is one cell and gets first_val. Otherwise, split it into four squares of side len / 2. Each quarter holds new_len * new_len numbers, so the quarters start at:
- upper-left:
first_val, at the samerowandcol; - upper-right:
first_valplus one quarter, shifted right bynew_lencolumns; - lower-left:
first_valplus two quarters, shifted down bynew_lenrows; - lower-right:
first_valplus three quarters, shifted both ways.
Because n is a power of 2, it halves evenly down to 1 and every split is exact.
Step by step
- Declare
fill_helperas a standalone function aboveimpl Solution. It takes the grid as&mut Vec<Vec<i32>>, a mutable reference so the writes are visible to the caller, plusrow,colandlenasusizeandfirst_valasi32. It returns nothing. - Base case. When
len == 1, setgrid[row][col]tofirst_val. - Recursive case. In the
elsebranch computenew_len = len / 2. - Upper-left: recurse with the same corner and the same first value.
- Upper-right: move the column by
new_lenand addnew_len * new_lento the first value. - Lower-left: move the row by
new_lenand add two quarters. - Lower-right: move both and add three quarters.
- In
z_pattern, build annbyngrid of zeros, a mutable vector of vectors. - Fill the whole grid as one square: corner (0, 0), side
n as usize, first value 1. Pass it as&mut grid. - Return the grid.
The solution in Rust
fn fill_helper(grid: &mut Vec<Vec<i32>>, row: usize, col: usize, len: usize, first_val: i32) {
if len == 1 {
grid[row][col] = first_val;
} else {
let new_len = len / 2;
fill_helper(grid, row, col, new_len, first_val);
fill_helper(
grid,
row,
col + new_len,
new_len,
first_val + (new_len * new_len) as i32,
);
fill_helper(
grid,
row + new_len,
col,
new_len,
first_val + 2 * (new_len * new_len) as i32,
);
fill_helper(
grid,
row + new_len,
col + new_len,
new_len,
first_val + 3 * (new_len * new_len) as i32,
);
}
}
impl Solution {
fn z_pattern(n: i32) -> Vec<Vec<i32>> {
let mut grid = vec![vec![0; n as usize]; n as usize];
fill_helper(&mut grid, 0, 0, n as usize, 1);
return grid;
}
}
The Rust details worth a closer look:
- A free function, not an associated one.
fill_helperlives outside theimplblock, so it is called by its plain name. Insideimpl Solution, a helper would be called asSelf::fill_helper. - Mutable references are passed on, not re-borrowed by hand.
gridinsidefill_helperis already a&mut Vec<Vec<i32>>, so the recursive calls pass it as it is. Rust re-borrows it for the duration of each call, and the four calls run one after another, so there is only one mutable borrow at any moment. Inz_patternthe grid is a plain owned vector, so the call writes&mut grid. usizefor positions,i32for values. Indexes and sizes must beusize, but the numbers in the grid arei32. Rust doesn't mix them, so(new_len * new_len) as i32converts the quarter size. The cast is applied to the product first, and only then is the result multiplied by 2 or 3 ini32.vec![vec![0; n]; n]. The innervec![0; n]builds one row, and the outer macro clones itntimes, so every row is its own independent vector. The element type is inferred asi32from the return type.return grid;works, though the idiomatic form is the bare expressiongridon the last line.
Complexity
Time: O(n^2). Every call either writes one cell or makes four calls on squares a quarter of the size. The recursion bottoms out at n * n single cells, and the work of splitting the squares above them adds about a third more, so the total stays proportional to the number of cells.
Space: O(n^2) for the result. The grid itself is the output. The recursion adds only O(log n) stack depth, because each call halves the side.
Edge cases and common mistakes
n = 1. The grid has one cell, the base case runs at once, and the result is[[1]].- Wrong order of the quadrants. Swapping lower-left and upper-right produces a different pattern, with the numbers running down before they run across. The order is upper-left, upper-right, lower-left, lower-right.
- Moving the wrong coordinate. The upper-right quadrant changes the column only, and the lower-left changes the row only. Mixing them up puts the numbers in the wrong places.
- Starting values. Each quadrant after the first begins
new_len * new_lennumbers later than the previous one. Usingnew_lenalone, orlen, leaves gaps and repeats. - A size that isn't a power of 2. The input is guaranteed to be one. With
n = 3, the splitting rounds down and the result is[[1, 2, 0], [3, 4, 0], [0, 0, 0]], with part of the grid left unfilled. - Forgetting
mut. The grid is modified, so it needslet mut, and the call needs&mut grid. A plain&gridis rejected by the compiler.
Testing
n = 1gives[[1]].n = 2gives[[1, 2], [3, 4]].n = 4gives the 4x4 grid shown above.n = 8has 1 to 16 in the upper-left 4x4 block, 17 to 32 in the upper-right, 33 to 48 in the lower-left and 49 to 64 in the lower-right, and its first row is[1, 2, 5, 6, 17, 18, 21, 22].
