Problem Description

You are given a string boxes of length n consisting of '0's and '1's. Each character represents a box, where '0' means the box is empty and '1' means the box contains one ball.

You can perform operations to move balls between boxes. In one operation, you can move one ball from a box to an adjacent box (a box that is exactly one position away, either to the left or right).

Your task is to calculate, for each box position i, the minimum total number of operations needed to move all balls in the string to that specific box i. Return an array answer where answer[i] represents this minimum number of operations for box i.

For example, if boxes = "110", there are balls at positions 0 and 1:

• To move all balls to position 0: move the ball from position 1 to position 0 (1 operation)
• To move all balls to position 1: move the ball from position 0 to position 1 (1 operation)
• To move all balls to position 2: move the ball from position 0 to position 1, then to position 2 (2 operations), and move the ball from position 1 to position 2 (1 operation), totaling 3 operations

The result would be [1, 1, 3].

Note that multiple balls can end up in the same box after operations, and each calculation starts from the initial configuration of boxes.

Intuition

To move all balls to a specific position i, we need to calculate the total distance each ball must travel. A ball at position j needs |i - j| operations to reach position i.

The key insight is that we can split this calculation into two parts:

• Balls to the left of position i need to move right
• Balls to the right of position i need to move left

For each position i, instead of recalculating from scratch, we can use dynamic programming to build upon previous calculations.

Consider moving from position i to position i+1. All balls that were to the left of position i are now one step further away from position i+1. If there are cnt balls to the left, the total cost increases by cnt. This observation allows us to maintain a running sum.

We can precompute two arrays:

• left[i]: total operations needed to move all balls from positions 0 to i-1 to position i
• right[i]: total operations needed to move all balls from positions i+1 to n-1 to position i

For left[i], we accumulate the cost as we move right. If we know left[i-1] (cost to move all balls to the left of i-1 to position i-1), then left[i] = left[i-1] + cnt, where cnt is the number of balls to the left of position i.

Similarly, for right[i], we work backwards from right to left.

The final answer for each position i is simply left[i] + right[i], combining the costs from both directions.

Learn more about Prefix Sum patterns.

Solution Approach

The solution uses dynamic programming with two auxiliary arrays to efficiently compute the minimum operations for each position.

Step 1: Initialize arrays

• Create two arrays left and right, both of size n, initialized with zeros
• left[i] will store the total operations to move all balls from positions 0 to i-1 to position i
• right[i] will store the total operations to move all balls from positions i+1 to n-1 to position i

Step 2: Build the left array

• Start from position 1 and iterate to the right
• Maintain a counter cnt for the number of balls seen so far to the left
• For each position i:
  • If boxes[i-1] == '1', increment cnt (found a ball at position i-1)
  • Calculate left[i] = left[i-1] + cnt
  • This works because moving from position i-1 to i, all cnt balls to the left need one additional operation

Step 3: Build the right array

• Start from position n-2 and iterate to the left
• Reset counter cnt to track balls to the right
• For each position i:
  • If boxes[i+1] == '1', increment cnt (found a ball at position i+1)
  • Calculate right[i] = right[i+1] + cnt
  • This accumulates the cost of moving all balls from the right to position i

Step 4: Combine results

• For each position i, the total minimum operations is left[i] + right[i]
• Return the combined array using list comprehension: [a + b for a, b in zip(left, right)]

Time Complexity: O(n) - We make two passes through the array Space Complexity: O(n) - We use two auxiliary arrays of size n

Example Walkthrough

Let's walk through the solution with boxes = "110":

Initial Setup:

• Input: boxes = "110" (balls at positions 0 and 1)
• Create arrays: left = [0, 0, 0] and right = [0, 0, 0]

Step 1: Build the left array

Starting from position 1, track balls to the left:

• Position 1:

  • Check boxes[0] = '1', so cnt = 1 (one ball to the left)
  • left[1] = left[0] + cnt = 0 + 1 = 1
  • This means moving 1 ball from position 0 to position 1 takes 1 operation

• Position 2:

  • Check boxes[1] = '1', so cnt = 2 (two balls to the left now)
  • left[2] = left[1] + cnt = 1 + 2 = 3
  • This means moving both balls to position 2 takes 3 total operations
  • (Ball at position 0 travels 2 steps = 2 ops, ball at position 1 travels 1 step = 1 op)

Result: left = [0, 1, 3]

Step 2: Build the right array

Starting from position 1 (going backwards), track balls to the right:

• Position 1:

  • Check boxes[2] = '0', so cnt = 0 (no balls to the right)
  • right[1] = right[2] + cnt = 0 + 0 = 0

• Position 0:

  • Check boxes[1] = '1', so cnt = 1 (one ball to the right)
  • right[0] = right[1] + cnt = 0 + 1 = 1
  • This means moving 1 ball from position 1 to position 0 takes 1 operation

Result: right = [1, 0, 0]

Step 3: Combine results

For each position, add left and right costs:

• Position 0: left[0] + right[0] = 0 + 1 = 1
• Position 1: left[1] + right[1] = 1 + 0 = 1
• Position 2: left[2] + right[2] = 3 + 0 = 3

Final Answer: [1, 1, 3]

This matches our expected result, where moving all balls to positions 0, 1, and 2 requires 1, 1, and 3 operations respectively.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the boxes string.

The algorithm consists of three main parts:

1. First forward pass from index 1 to n-1: O(n) iterations
2. Second backward pass from index n-2 to 0: O(n) iterations
3. Final list comprehension to combine left and right arrays: O(n) iterations

Each iteration performs constant time operations (comparisons, additions, array assignments). Therefore, the total time complexity is O(n) + O(n) + O(n) = O(n).

Space Complexity: O(n)

The algorithm uses:

• left array of size n: O(n) space
• right array of size n: O(n) space
• The output list (result of zip operation) of size n: O(n) space
• Two counter variables cnt: O(1) space

The total auxiliary space used is O(n) + O(n) = O(n). Note that if we don't count the output array as extra space (as it's required for the answer), the space complexity remains O(n) due to the left and right arrays.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Ball Counting

Pitfall: A common mistake is incorrectly tracking when to count balls. Developers often confuse whether to check boxes[i] or boxes[i-1] when building the left array, and similarly for the right array.

Why it happens: The confusion arises because we're calculating the cost for position i, but we need to count balls that are NOT at position i itself.

Incorrect approach:

# WRONG: Checking current position instead of previous
for i in range(1, n):
    if boxes[i] == '1':  # This is wrong!
        balls_count += 1
    left_cost[i] = left_cost[i - 1] + balls_count

Correct approach:

# CORRECT: Check previous position for left array
for i in range(1, n):
    if boxes[i - 1] == '1':  # Check the position we're moving FROM
        balls_count += 1
    left_cost[i] = left_cost[i - 1] + balls_count

2. Incorrect Initialization or Range Boundaries

Pitfall: Starting the loops from wrong indices or using incorrect range boundaries, especially for the right array calculation.

Incorrect approach:

# WRONG: Starting from wrong index or going to wrong boundary
for i in range(n - 1, 0, -1):  # Missing index 0!
    if boxes[i + 1] == '1':
        balls_count += 1
    right_cost[i] = right_cost[i + 1] + balls_count

Correct approach:

# CORRECT: Process from n-2 down to 0 (inclusive)
for i in range(n - 2, -1, -1):
    if boxes[i + 1] == '1':
        balls_count += 1
    right_cost[i] = right_cost[i + 1] + balls_count

3. Reusing the Same Counter Variable

Pitfall: Forgetting to reset the balls_count variable between calculating left and right arrays.

Incorrect approach:

balls_count = 0
# Calculate left costs
for i in range(1, n):
    if boxes[i - 1] == '1':
        balls_count += 1
    left_cost[i] = left_cost[i - 1] + balls_count

# WRONG: Forgot to reset balls_count!
# balls_count still has value from left calculation
for i in range(n - 2, -1, -1):
    if boxes[i + 1] == '1':
        balls_count += 1
    right_cost[i] = right_cost[i + 1] + balls_count

Solution: Always reset the counter before starting the second loop:

balls_count = 0  # Reset before calculating right costs

4. Misunderstanding the Problem Statement

Pitfall: Thinking that balls disappear after moving them or that we need to track individual ball movements rather than calculating the total distance.

Key insight: Each position's answer is independent - we always start from the original configuration and calculate the total operations needed to move ALL balls to that specific position. The balls don't actually move between calculations.