Sponsored
Sponsored
In this approach, first simulate the effect of gravity on the stones in the box before rotating the box 90 degrees clockwise. To simulate gravity, traverse each row from right to left, moving stones to the right until they hit an obstacle or stack upon other stones. Once every stone has settled due to gravity, create a new matrix representing the rotated box by converting rows into columns.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. This complexity comes from the need to process each element when simulating gravity and then again when transposing.
Space Complexity: O(1) if we ignore the space for the output result that is unavoidable for transposing the matrix.
1def rotateBox(boxGrid):
2 m, n = len(boxGrid), len(boxGrid[0])
3 for r in range(m):
4 # Apply gravity
5 free_space = n - 1
6 for c in range(n - 1, -1, -1):
7 if boxGrid[r][c] == '#':
8 boxGrid[r][free_space], boxGrid[r][c] = '#', '.'
9 free_space -= 1
10 elif boxGrid[r][c] == '*':
11 free_space = c - 1
12 # Rotate the box 90 degrees clockwise
13 rotated_box = zip(*boxGrid[::-1])
14 return [list(row) for row in rotated_box]This Python solution iterates through each row of the box matrix from right to left, simulating the effect of gravity by moving stones ('#') to the rightmost available positions and stopping if an obstacle ('*') is encountered. After gravity is applied, the matrix is transposed to achieve a 90 degrees clockwise rotation.
This approach creates a new matrix to represent the rotated version of the box. After initializing the new transposed matrix, simulate the gravitational fall of each stone by placing them in the correct positions in the new matrix. This is achieved by iterating through the rotated columns and calculating the final position of each stone.
Time Complexity: O(m * n) because transposing and simulating stone drops require us to iterate through all elements.
Space Complexity: O(m * n) for storing the rotated matrix.
1import java.util.Arrays;
2
The Java solution pre-allocates a rotated matrix, initializes it with empty spaces, and directly simulates the effects of gravity as each stone is repositioned in the rotated matrix. This approach eliminates the need for a separate gravity simulation phase before rotation.