Rotating the Box

Medium
907.

Rotating the Box

Rotating the Box is a medium coding problem on arrays, matrix and two pointers, asked in Amazon, Microsoft, Zoho and Capital One interviews.

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 '.'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} grid
 * @return {string[]}
 */
var rotateTheBox = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Rotating the Box — Solution in Python, Java & C++

Rotating the Box solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and matrix.

Rotating the Box is a medium coding problem on arrays, matrix and two pointers, asked in Amazon, Microsoft, Zoho and Capital One interviews.

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 '.'

Hints for Rotating the Box

  1. Hint 1

    Rotating clockwise turns each original row into a column, so gravity acts along the original rows — towards the right end.

  2. Hint 2

    Settle the stones in the original orientation first, then rotate; doing it the other way round is far messier.

  3. Hint 3

    Sweep each row from right to left, tracking the rightmost free slot; an obstacle resets it.

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

  1. For each row, keep empty at the rightmost slot a stone may fall into, starting at n - 1.
  2. Walk right to left: an obstacle sets empty = j - 1; a stone moves to empty and decrements it; a gap is skipped.
  3. 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)]

Java

public static String[] rotateTheBox(String[] grid) {
    int m = grid.length, n = grid[0].length();
    char[][] rows = new char[m][];
    for (int i = 0; i < m; i++) rows[i] = grid[i].toCharArray();
    for (int i = 0; i < m; i++) {
        int empty = n - 1;
        for (int 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--;
            }
        }
    }
    String[] out = new String[n];
    for (int j = 0; j < n; j++) {
        StringBuilder sb = new StringBuilder();
        for (int i = m - 1; i >= 0; i--) sb.append(rows[i][j]);
        out[j] = sb.toString();
    }
    return out;
}

C++

vector<string> rotateTheBox(vector<string>& grid) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    vector<string> rows = grid;
    for (int i = 0; i < m; i++) {
        int empty = n - 1;
        for (int 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--;
            }
        }
    }
    vector<string> out;
    for (int j = 0; j < n; j++) {
        string s;
        for (int i = m - 1; i >= 0; i--) s += rows[i][j];
        out.push_back(s);
    }
    return out;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal