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.
- Difficulty: Medium
- Topics: Arrays, Matrix, Two Pointers, Simulation
- Asked at: Amazon, Microsoft, Zoho, Capital One
- 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.lengthn == grid[i].length1 <= m, n <= 500grid[i][j] is '#', '*' or '.'
Hints for Rotating the Box
Hint 1
Rotating clockwise turns each original row into a column, so gravity acts along the original rows — towards the right end.
Hint 2
Settle the stones in the original orientation first, then rotate; doing it the other way round is far messier.
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
- For each row, keep
emptyat the rightmost slot a stone may fall into, starting atn - 1. - Walk right to left: an obstacle sets
empty = j - 1; a stone moves toemptyand decrements it; a gap is skipped. - Rotate by reading column
jbottom-to-top into output rowj.
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 = jinstead ofj - 1at an obstacle lets a stone overwrite it. - The rotation reads rows bottom-to-top: output row
jisgrid[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