Rotating the Box — Medium Problem & Solution

A grid of stones is given as rows of characters: # is a stone, is a fixed obstacle and . is empty.

Difficulty: Medium
Topics: Arrays, Two Pointers, Matrix, Simulation
Asked at: Amazon, Microsoft, Zoho
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A grid of stones is given as rows of characters: # is a stone, * is a fixed obstacle and . is empty.

The grid is rotated 90° clockwise, then gravity pulls every stone straight down until it rests on the bottom, on an obstacle, or on another stone. Obstacles never move. Return the rows of the grid after the rotation has settled.

Example 1

Input: grid = ["#.#"]
Output: [".","#","#"]
Explanation: One row becomes one column; the two stones settle at the bottom.

Example 2

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

Example 3

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

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 500
grid[i][j] is '#', '*' or '.'

How to solve Rotating the Box

Do gravity before the rotation. After a clockwise turn, "down" in the rotated grid is "right" in the original, so one right-to-left sweep per row settles everything. The rotation is then a plain index transpose.

Approach

For each row, keep empty at the rightmost slot a stone may fall into, starting at n - 1.
Walk right to left: an obstacle sets empty = j - 1; a stone moves to empty and decrements it; a gap is skipped.
Rotate by reading column j bottom-to-top into output row j.

Why it works

The empty pointer only ever moves left, so each row is settled in a single pass: every stone lands in the leftmost-unfilled position to its right, which is precisely where gravity would leave it once the grid is turned. An obstacle blocks the whole column beneath it after the turn, which is why it resets the pointer rather than being skipped.

Complexity

Time — O(m · n)
Space — O(m · n) for the output

Pitfalls

Applying gravity after rotating needs a bottom-up sweep per column and is easy to get wrong.
Setting empty = j instead of j - 1 at an obstacle lets a stone overwrite it.
The rotation reads rows bottom-to-top: output row j is grid[m-1][j] … grid[0][j].

Reference solution

Python

from typing import List

def rotateTheBox(grid: List[str]) -> List[str]:
    m, n = len(grid), len(grid[0])
    rows = [list(r) for r in grid]
    for i in range(m):
        empty = n - 1
        for j in range(n - 1, -1, -1):
            if rows[i][j] == '*':
                empty = j - 1
            elif rows[i][j] == '#':
                rows[i][j] = '.'
                rows[i][empty] = '#'
                empty -= 1
    return [''.join(rows[i][j] for i in range(m - 1, -1, -1)) for j in range(n)]

JavaScript

var rotateTheBox = function(grid) {
    var m = grid.length, n = grid[0].length, i, j;
    var rows = [];
    for (i = 0; i < m; i++) rows.push(grid[i].split(""));
    for (i = 0; i < m; i++) {
        var empty = n - 1;
        for (j = n - 1; j >= 0; j--) {
            if (rows[i][j] === "*") empty = j - 1;
            else if (rows[i][j] === "#") {
                rows[i][j] = ".";
                rows[i][empty] = "#";
                empty--;
            }
        }
    }
    var out = [];
    for (j = 0; j < n; j++) {
        var s = "";
        for (i = m - 1; i >= 0; i--) s += rows[i][j];
        out.push(s);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue