We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Where Will the Ball Fall

Number: 1324

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an m x n grid representing a box with diagonally placed boards (either directing the ball to the left or to the right), we drop one ball in each column at the top. As the ball moves down the grid, the board in each cell redirects its path. A ball may either fall out of the bottom of the box or get stuck if it either encounters a V-shaped blockage or is directed into a wall. The task is to determine, for each ball dropped, from which column it will exit at the bottom or if it becomes stuck (indicated by -1).

Key Insights

  • Simulation problem where each ball's path is followed row by row.
  • At every cell, check the board's direction and update the column accordingly.
  • The ball gets stuck if it moves out of bounds or if the next cell's board creates a "V" shape trap (i.e. the current board's direction and the adjacent board's direction are different).
  • Iteratively simulate for each ball starting at every column of the top row.

Space and Time Complexity

Time Complexity: O(m * n) because for each of n balls, we simulate movement through m rows. Space Complexity: O(n) for the result array, while additional space used is constant.

Solution

The algorithm simulates the movement of each ball by iterating through the grid row by row. For each ball:

  1. Initialize the current column as the starting column.
  2. For every row, use the value in the cell (either 1 or -1) to determine the next column.
  3. Check two conditions:
    • If moving in the indicated direction goes out of bounds.
    • If the adjacent cell in the same row does not have the same board value (indicating a V-shaped trap).
  4. If either condition is met, the ball gets stuck; otherwise, continue to the next row.
  5. After processing all rows, the final column is recorded, or -1 if the ball became stuck.

This simulation uses simple iterative loops and conditional checks without additional data structures.

Code Solutions

# Python solution with line-by-line comments
def findBall(grid):
    # Number of rows and columns in the grid
    m, n = len(grid), len(grid[0])
    result = []
    
    # Process each ball starting from each column at the top
    for starting_col in range(n):
        col = starting_col  # current column for the ball
        # Simulate the ball's journey through each row in the grid
        for row in range(m):
            direction = grid[row][col]  # get the current board's direction (1 or -1)
            next_col = col + direction  # compute next column based on board's direction

            # Check if the ball goes out of bounds or into a V-shaped trap
            if next_col < 0 or next_col >= n or grid[row][next_col] != direction:
                col = -1  # ball gets stuck
                break
            col = next_col  # update current column to next position
        result.append(col)  # store final column (or -1 if stuck)
    
    return result

# Example usage:
# grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],
#         [-1,-1,-1,1,1],[1,1,1,1,-1],
#         [-1,-1,-1,-1,-1]]
# print(findBall(grid))
← Back to All Questions