Rotating the Box

medium matrix two pointers

Problem

Given an m×n box of '#' (stones), '*' (obstacles), '.' (empty), rotate 90° clockwise and let gravity settle the stones to the right (originally bottom).

Inputbox = [["#",".","#"]]

Output[["."],["#"],["#"]]

After gravity: '..##' becomes '..##' before rotation; rotated → columns of stones at bottom.

box (rows ';' chars from #*.)

def rotate_the_box(box):
    m, n = len(box), len(box[0])
    for row in box:
        write = n - 1
        for c in range(n - 1, -1, -1):
            if row[c] == '*':
                write = c - 1
            elif row[c] == '#':
                row[write], row[c] = '#', ('.' if write != c else '#')
                write -= 1
    # rotate 90 cw
    return [[box[m - 1 - r][c] for r in range(m)] for c in range(n)]

function rotateTheBox(box) {
  const m = box.length, n = box[0].length;
  for (const row of box) {
    let write = n - 1;
    for (let c = n - 1; c >= 0; c--) {
      if (row[c] === '*') write = c - 1;
      else if (row[c] === '#') {
        row[write] = '#';
        if (write !== c) row[c] = '.';
        write--;
      }
    }
  }
  const out = Array.from({length: n}, () => new Array(m));
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      out[c][m - 1 - r] = box[r][c];
  return out;
}

class Solution {
    public char[][] rotateTheBox(char[][] box) {
        int m = box.length, n = box[0].length;
        for (char[] row : box) {
            int write = n - 1;
            for (int c = n - 1; c >= 0; c--) {
                if (row[c] == '*') write = c - 1;
                else if (row[c] == '#') {
                    row[write] = '#';
                    if (write != c) row[c] = '.';
                    write--;
                }
            }
        }
        char[][] out = new char[n][m];
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                out[c][m - 1 - r] = box[r][c];
        return out;
    }
}

vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
    int m = box.size(), n = box[0].size();
    for (auto& row : box) {
        int write = n - 1;
        for (int c = n - 1; c >= 0; c--) {
            if (row[c] == '*') write = c - 1;
            else if (row[c] == '#') { row[write] = '#'; if (write != c) row[c] = '.'; write--; }
        }
    }
    vector<vector<char>> out(n, vector<char>(m));
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            out[c][m - 1 - r] = box[r][c];
    return out;
}

Explanation

This problem combines gravity with a rotation, but the clean trick is to settle the stones before rotating, while everything is still in simple row form. After the 90° clockwise turn, "down" becomes "right", so in the original layout we let stones fall toward the right end of each row.

For each row we sweep from right to left with a write pointer that marks where the next falling stone should land. When we hit a stone '#', we move it to the write slot and step write left. When we hit an obstacle '*', stones cannot pass it, so we reset write to just left of the obstacle (write = c - 1). Empty cells '.' are skipped over, which is exactly how stones fall past gaps.

Once every row has settled, we perform the actual 90° clockwise rotation: the new cell out[c][m-1-r] takes the value from box[r][c]. This maps each original position to where it belongs after turning.

Example: a row "#.#" with no obstacle settles its two stones to the right as ".##"; after the rotation those stones end up stacked at the bottom of a column, which is what gravity should produce.

Each cell is visited a constant number of times across settling and rotation, so the work scales with the number of cells.

Time: O(m·n) Space: O(m·n)