0625MediumArrayMatrixSimulation

Stamping the Courtyard Slabs

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A paving crew is laying a square courtyard of side rows by side columns of slabs. Every slab gets a stamped number recording the order it was bedded down, starting at 1 and rising by one for each slab.

The crew works inwards in a spiral. Starting at the slab in the north-west corner they bed the whole top row eastwards, then turn and work down the far-east column southwards, then back along the bottom row westwards, then up the west column northwards, stopping just below the row they started on. That closes one ring. They then repeat the same four legs on the ring of still-bare slabs inside it, and carry on until no bare slab is left.

Return the stamped numbers as a grid of side rows, each row read from west to east.

Examples

Example 1

Input: side = 4
Output: [[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]

The top row is stamped 1 to 4 west to east, the east column carries on with 5 to 7 going south, the bottom row takes 8 to 10 heading west, and the west column takes 11 and 12 heading north, which closes the outer ring. The four slabs left in the middle are stamped 13 to 16 the same way.

Example 2

Input: side = 2
Output: [[1, 2], [4, 3]]

The top row takes 1 and 2, the east column takes 4's predecessor 3 below the 2, and the bottom row takes 4 under the 1, so the single ring uses every slab.

Example 3

Input: side = 5
Output: [[1, 2, 3, 4, 5], [16, 17, 18, 19, 6], [15, 24, 25, 20, 7], [14, 23, 22, 21, 8], [13, 12, 11, 10, 9]]

The outer ring uses stamps 1 to 16, the next ring in uses 17 to 24, and the one slab at the centre of the courtyard takes stamp 25.

Constraints

1 <= side <= 20

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def lay_slabs(side: int) -> list[list[int]]:

Java

public int[][] laySlabs(int side)

The intended approach

Time O(side^2): each slab is stamped exactly once.Space O(1) beyond the returned grid; only the four edge markers and the running stamp are kept.

Hold the ring still to be bedded as four moving edges: the topmost bare row, the bottommost bare row, and the westmost and eastmost bare columns. Each pass stamps the top row eastwards and pulls that edge down, stamps the east column southwards and pulls that edge in, then does the same for the bottom row westwards and the west column northwards. Because a ring of a square courtyard is itself square, the two edges close in together and the emptied legs simply iterate over nothing once one slab is left, so the middle slab of an odd courtyard is stamped by the first leg alone.

Pythonentry point: lay_slabs

def lay_slabs(side):
    # walk the four edges of the ring that is still bare, then close the ring inwards
    court = [[0] * side for _ in range(side)]
    top, bottom, left, right = 0, side - 1, 0, side - 1
    stamp = 1
    while top <= bottom and left <= right:
        for col in range(left, right + 1):
            court[top][col] = stamp
            stamp += 1
        top += 1
        for row in range(top, bottom + 1):
            court[row][right] = stamp
            stamp += 1
        right -= 1
        for col in range(right, left - 1, -1):
            court[bottom][col] = stamp
            stamp += 1
        bottom -= 1
        for row in range(bottom, top - 1, -1):
            court[row][left] = stamp
            stamp += 1
        left += 1
    return court

The obvious version

Walk one slab at a time carrying a heading. Stamp the current slab, then look at the slab straight ahead: if it is off the courtyard or already stamped, turn a quarter turn clockwise first. Repeat until every slab carries a stamp.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_lay_slabs(side):
    court = [[0] * side for _ in range(side)]
    heading = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    row = col = face = 0
    for stamp in range(1, side * side + 1):
        court[row][col] = stamp
        drow, dcol = heading[face]
        nrow, ncol = row + drow, col + dcol
        if not (0 <= nrow < side and 0 <= ncol < side and court[nrow][ncol] == 0):
            face = (face + 1) % 4
            drow, dcol = heading[face]
            nrow, ncol = row + drow, col + dcol
        row, col = nrow, ncol
    return court

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in