Similar Problems

Similar Problems not available

Rotating The Box - Leetcode Solution

Companies:

LeetCode:  Rotating The Box Leetcode Solution

Difficulty: Medium

Topics: matrix array two-pointers  

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

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

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 of the stones does not allow a stone to move left or right.

Example:

Input: box = [["#",".","#"]] Output: [["."], ["#"], ["#"]]

Solution:

  1. Iterate through each row of the input box.
  2. For each row, iterate through each column from right to left.
  3. If a stone '#' character is found, check if there is space below it in the current column.
  4. If there is empty '.', move the stone down to the empty space and set the original location to empty.
  5. If there is an obstacle '*' or another stone '#', check if there is empty space to the left of the obstacle/stone.
  6. If there is empty space to the left, move the stone to the empty space and set the original location to empty.
  7. If there is no empty space to the left, the stone remains in its original position.
  8. After iterating through all rows and columns, return the rotated box.

Sample code:

class Solution: def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:

    # Helper function to move stone to new location and set original location to empty
    def move_stone(box: List[List[str]], row: int, col: int, new_row: int, new_col: int) -> None:
        box[new_row][new_col] = '#'
        box[row][col] = '.'
    
    m, n = len(box), len(box[0])
    
    # Iterate through each row
    for i in range(m):
        row = box[i]
        j = n - 1
        k = n - 1
        
        # Iterate through each column from right to left
        while j >= 0:
            
            # If stone is found in current column, check if there is space below it
            if row[j] == '#':
                if j < k:
                    k = j
                
                if j == 0 or row[j-1] != '#':
                    empty_row = i
                    
                    # Move stone down to empty space
                    while empty_row < m and box[empty_row][j] == '.':
                        move_stone(box, empty_row, j, empty_row-1, j)
                        empty_row += 1
                    
                    # Check if there is obstacle or stone to the left
                    if j > 0 and (box[empty_row-1][j-1] == '#' or box[empty_row-1][j-1] == '*'):
                        k = j - 1
                
                # Move stone to empty space to the left
                if k < j:
                    empty_row = i
                    
                    while empty_row < m and box[empty_row][k] == '.':
                        move_stone(box, empty_row, j, empty_row, k)
                        empty_row += 1
                    
                    k -= 1
            
            j -= 1
    
    # Rotate box 90 degrees clockwise
    rotated_box = [[0] * m for _ in range(n)]
    
    for i in range(n):
        for j in range(m):
            rotated_box[i][j] = box[m-j-1][i]
    
    return rotated_box

Time Complexity: The code iterates through each element in the input box once, so the time complexity is O(m*n), where m and n are the dimensions of the input box.

Space Complexity: The code creates a new rotated_box with dimensions nm, so the space complexity is O(mn).

Rotating The Box Solution Code

1