0356MediumArrayTwo PointersMatrix

Turned Bearing Crate

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 crate is packed into cells, given as boxGrid with one one-character string per cell:

"#" is a loose ball bearing,
"*" is a strut fixed to the crate,
"." is an empty cell.

A handler tips the crate a quarter turn clockwise, so the column that was leftmost ends up as the top row. The struts stay bolted where they are, and once the crate is at rest every bearing has slid straight down as far as it can go, stopping on the crate floor, on a strut, or on another bearing that has already come to rest.

Return the cells of the crate after the turn and the settling. If boxGrid has m rows and n columns, the answer has n rows and m columns.

Examples

Example 1

Input: boxGrid = [["#","#",".","*","#"]]
Output: [["."],["#"],["#"],["*"],["#"]]

The single row becomes a single column, top to bottom in the order the row ran. The two bearings left of the strut come to rest on top of it, and the bearing on the far side of the strut lands on the crate floor.

Example 2

Input: boxGrid = [["#","."],[".","#"],["*","."]]
Output: [["*",".","."],[".","#","#"]]

The turn puts the old first column across the top row, so the strut lands at the top left. Both bearings end up on the bottom row of the turned crate.

Example 3

Input: boxGrid = [[".","#","#"],["*",".","#"],[".",".","."]]
Output: [[".","*","."],[".",".","#"],[".","#","#"]]

The bearing that shared a row with the strut settles into the bottom right area, and the two bearings from the first row of the crate finish in the last two rows of the last column.

Constraints

m == boxGrid.length
n == boxGrid[r].length
1 <= m, n <= 500
boxGrid[r][c] is "#", "*" or ".".

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 rotate_the_box(boxGrid: list[list[str]]) -> list[list[str]]:

Java

public char[][] rotateTheBox(char[][] boxGrid)

The intended approach

Time O(m * n)Space O(m * n)

A quarter turn clockwise sends the right-hand end of each original row to the bottom of the crate, so the settling can be done before the turn: walk each row from its right end while remembering the next free resting cell, move each bearing there, and reset that marker to just left of any strut you pass. Copying the settled rows into columns then applies the turn.

Pythonentry point: rotate_the_box

def rotate_the_box(boxGrid):
    # Before the turn, "down" for a bearing means the right-hand end of its own row,
    # so settle each row with one right-to-left walk that remembers the next free
    # resting slot and resets that slot whenever a strut is passed.  Then copy the
    # settled crate out under the clockwise turn.
    # Time O(m * n).  Space O(m * n) for the settled copy and the returned crate.
    rows = len(boxGrid)
    cols = len(boxGrid[0])
    settled = [row[:] for row in boxGrid]
    for r in range(rows):
        row = settled[r]
        free = cols - 1
        for c in range(cols - 1, -1, -1):
            if row[c] == "*":
                free = c - 1
            elif row[c] == "#":
                row[c] = "."
                row[free] = "#"
                free -= 1
    turned = []
    for c in range(cols):
        turned.append([settled[rows - 1 - r][c] for r in range(rows)])
    return turned

The obvious version

Turn the crate first, then keep sweeping it from the bottom up, sliding any bearing that has an empty cell directly below it down one place, until a full sweep moves nothing.

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_turn_and_drop(boxGrid):
    rows = len(boxGrid)
    cols = len(boxGrid[0])
    turned = []
    for c in range(cols):
        turned.append([boxGrid[rows - 1 - r][c] for r in range(rows)])
    height = cols
    width = rows
    moved = True
    while moved:
        moved = False
        for r in range(height - 2, -1, -1):
            for c in range(width):
                if turned[r][c] == "#" and turned[r + 1][c] == ".":
                    turned[r][c] = "."
                    turned[r + 1][c] = "#"
                    moved = True
    return turned

How this problem was checked

Reference solution executed against 9 test cases — 9 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