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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Operations to Move All Balls to Each Box

Difficulty: Medium

Problem Description

You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the i-th box is empty, and '1' if it contains one ball. In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1. Note that after doing so, there may be more than one ball in some boxes. Return an array answer of size n, where answer[i] is the minimum number of operations needed to move all the balls to the i-th box. Each answer[i] is calculated considering the initial state of the boxes.

Key Insights

  • The problem requires calculating the minimum operations to move all balls to each box.
  • Operations are only allowed between adjacent boxes.
  • We can use a prefix sum approach to calculate the number of operations for each box efficiently.
  • The number of operations for a box depends on the number of balls to its left and right and their distances.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can use two passes through the boxes string. In the first pass, we calculate the total number of operations required to move all balls to each box considering only left-side balls. In the second pass, we do the same for the right-side balls.

  1. Left-to-Right Pass: Maintain a count of the number of balls encountered so far and the cumulative operations needed to move those balls to the current box.
  2. Right-to-Left Pass: Similarly, maintain a count for the right side and update the operations needed by considering the right-side balls.

By combining the results from both passes, we can get the total operations needed for each box.

Code Solutions

def minOperations(boxes: str) -> List[int]:
    n = len(boxes)
    answer = [0] * n
    
    # Left to right pass
    left_balls = 0
    operations = 0
    for i in range(n):
        answer[i] += operations
        if boxes[i] == '1':
            left_balls += 1
        operations += left_balls
    
    # Right to left pass
    right_balls = 0
    operations = 0
    for i in range(n - 1, -1, -1):
        answer[i] += operations
        if boxes[i] == '1':
            right_balls += 1
        operations += right_balls
    
    return answer
← Back to All Questions