Rotating the Box - Practice Coding Problems

Rotating the Box - Problem

You are given an m x n matrix of characters boxGrid representing a side-view of a box. Each cell of the box is one of the following:

A stone '#'
A stationary obstacle '*'
Empty '.'

The box is rotated 90 degrees clockwise, causing some of the stones to fall due to gravity. Each stone falls down until it lands on an obstacle, another stone, or the bottom of the box. Gravity does not affect the obstacles' positions, and the inertia from the box's rotation does not affect the stones' horizontal positions.

It is guaranteed that each stone in boxGrid rests on an obstacle, another stone, or the bottom of the box.

Return an n x m matrix representing the box after the rotation described above.

Input & Output

Example 1 — Basic 3x3 Box

$ Input: boxGrid = [[".""#","#"],[".","#","#"],[".","#","."]]

› Output: [["#",".","."],["#","#","*"],["#","#","."]]

💡 Note: After rotation, stones in columns 1&2 fall down. Column 0 has obstacle '*' blocking some stones.

Example 2 — Single Row

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

› Output: [["#"],["#"],["*"],["."],["."]]

💡 Note: Single row becomes a column. Stones fall to bottom, obstacle stays in place.

Example 3 — All Obstacles

$ Input: boxGrid = [["*","*"],["*","*"]]

› Output: [["*","*"],["*","*"]]

💡 Note: Obstacles don't move during rotation, so result is just rotated positions.

Constraints

m == boxGrid.length
n == boxGrid[i].length
1 ≤ m, n ≤ 500
boxGrid[i][j] is either '.', '#', or '*'

Visualization

Tap to expand

Understanding the Visualization

Input Box

3×3 matrix with stones (#), obstacles (*), and empty spaces (.)

Apply Gravity & Rotate

Stones fall due to gravity, then entire box rotates 90° clockwise

Final Result

3×3 result matrix showing new positions after transformation

Key Takeaway

🎯 Key Insight: Handle gravity first within rows using two pointers, then rotate - much simpler than rotating first then simulating falling stones individually

Asked in

a Amazon 45 M Microsoft 32 G Google 28 f Meta 22

The key insight is to handle gravity first within each row using two pointers, then rotate the matrix. This is much cleaner than rotating first and simulating falling. Best approach uses gravity-first with two pointers: Time: O(m×n), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ Rotate Then Simulate Falling	O(m × n × max(m,n))	O(m × n)	Rotate the matrix first, then simulate each stone falling individually
Gravity First, Then Rotate	O(m × n)	O(m × n)	Apply gravity to each row using two pointers, then rotate the result

Rotate Then Simulate Falling — Algorithm Steps

Step 1: Create rotated matrix (90° clockwise)
Step 2: For each stone in rotated matrix, simulate falling
Step 3: Move stone down until it hits obstacle or bottom

Visualization

Tap to expand

Step-by-Step Walkthrough

Original Matrix

3x3 box with stones and obstacles

After Rotation

Matrix rotated 90° clockwise

After Gravity

Stones fall down to their final positions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char** solution(char** boxGrid, int boxGridSize, int* boxGridColSize, int* returnSize, int** returnColumnSizes) {
    int m = boxGridSize;
    int n = boxGridColSize[0];
    
    *returnSize = n;
    *returnColumnSizes = (int*)malloc(n * sizeof(int));
    
    // Allocate result matrix
    char** result = (char**)malloc(n * sizeof(char*));
    for (int i = 0; i < n; i++) {
        result[i] = (char*)malloc(m * sizeof(char));
        (*returnColumnSizes)[i] = m;
    }
    
    // Step 1: Rotate 90 degrees clockwise
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            result[j][m-1-i] = boxGrid[i][j];
        }
    }
    
    // Step 2: Simulate falling for each stone
    for (int j = 0; j < m; j++) {  // For each column
        for (int i = n-2; i >= 0; i--) {  // From bottom to top
            if (result[i][j] == '#') {
                // Find where this stone should fall
                int fallPos = i;
                while (fallPos + 1 < n && result[fallPos + 1][j] == '.') {
                    fallPos++;
                }
                
                // Move stone to fall position
                if (fallPos != i) {
                    result[fallPos][j] = '#';
                    result[i][j] = '.';
                }
            }
        }
    }
    
    return result;
}

int main() {
    // Simplified implementation
    printf("[[\"#\"],[\"#\"],[\"*\"],[\".\"],[\".\"],[\"#\"],[\".\"],[\".\"],[\"#\"]]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n × max(m,n))

Rotation takes O(m×n), then each stone may fall up to max(m,n) positions

✓ Linear Growth

Space Complexity

O(m × n)

Extra space for rotated matrix

⚡ Linearithmic Space

35.4K Views

Medium Frequency

~25 min Avg. Time

987 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Rotate Then Simulate Falling — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler