Problem Description

You are given a binary string boxes of length n, where each character represents a box: '1' means the box contains a ball, and '0' means it is empty.

Your task is to return an integer array answer of length n, where answer[i] is the minimum number of operations needed to move all balls to the i-th box.

In one operation, you can pick up a ball from any box and move it to any other box. The cost of moving a ball from box i to box j is |i - j| (the absolute difference of their indices).

• There is exactly one valid answer for each input.
• You may not reuse or split balls; each ball must be moved individually.
• Your answer array should not modify the original input.

Thought Process

The brute-force approach is straightforward: for each box, calculate the total cost to bring every ball to that box. This means, for every index, you check all other indices, and if there's a ball, you add the distance to the current index.

However, this results in a nested loop, leading to O(n²) time complexity. For small inputs, this is fine, but for larger inputs, it's inefficient.

To optimize, we can recognize that the cost for each box can be computed efficiently by scanning from left to right and right to left, accumulating the number of balls seen so far and their total movement cost. This way, we avoid redundant calculations and bring the complexity down to O(n).

Solution Approach

The optimized solution uses two passes over the input string:

1. Left-to-right pass:
   • Keep a running count of balls seen so far (balls).
   • Keep a running total of the cost to move all balls to the current position (moves).
   • For each box, store the current moves as the partial answer, then update balls and moves for the next position.
2. Right-to-left pass:
   • Repeat the process, but now from right to left, adding the cost to the existing partial answer from the first pass.
   • This accounts for all balls to the right of the current box.

By summing the costs from both passes, we get the minimum number of operations for each box.

This approach is efficient because:

• Each pass is O(n), so the total time is O(n).
• No extra data structures are needed beyond the answer array.

Example Walkthrough

Let's use the input boxes = "110".

1. Left-to-right pass:
   • Start with moves = 0, balls = 0.
   • At index 0: box has a ball ('1'), so balls += 1. Store moves = 0 in answer[0].
   • At index 1: add balls to moves (moves = 1), box has a ball, so balls += 1. Store moves = 1 in answer[1].
   • At index 2: add balls to moves (moves = 3), box is empty. Store moves = 3 in answer[2].

   After this pass, answer = [0, 1, 3]

2. Right-to-left pass:
   • Reset moves = 0, balls = 0.
   • At index 2: box is empty, store moves = 3 (no change).
   • At index 1: add balls to moves (moves = 0), box has a ball, so balls += 1. Add moves to answer[1] (answer[1] = 1).
   • At index 0: add balls to moves (moves = 1), box has a ball, so balls += 1. Add moves to answer[0] (answer[0] = 1).

   Final answer = [1, 1, 3]

This matches the expected output: [1, 1, 3]

Code Implementation

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        answer = [0] * n
        moves = balls = 0
        
        # Left to right
        for i in range(n):
            answer[i] += moves
            balls += int(boxes[i])
            moves += balls
        
        moves = balls = 0
        # Right to left
        for i in range(n-1, -1, -1):
            answer[i] += moves
            balls += int(boxes[i])
            moves += balls
        
        return answer
      

class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.size();
        vector<int> answer(n, 0);
        int moves = 0, balls = 0;
        // Left to right
        for (int i = 0; i < n; ++i) {
            answer[i] += moves;
            balls += boxes[i] - '0';
            moves += balls;
        }
        moves = balls = 0;
        // Right to left
        for (int i = n - 1; i >= 0; --i) {
            answer[i] += moves;
            balls += boxes[i] - '0';
            moves += balls;
        }
        return answer;
    }
};
      

class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] answer = new int[n];
        int moves = 0, balls = 0;
        // Left to right
        for (int i = 0; i < n; ++i) {
            answer[i] += moves;
            balls += boxes.charAt(i) - '0';
            moves += balls;
        }
        moves = balls = 0;
        // Right to left
        for (int i = n - 1; i >= 0; --i) {
            answer[i] += moves;
            balls += boxes.charAt(i) - '0';
            moves += balls;
        }
        return answer;
    }
}
      

var minOperations = function(boxes) {
    const n = boxes.length;
    const answer = new Array(n).fill(0);
    let moves = 0, balls = 0;
    // Left to right
    for (let i = 0; i < n; ++i) {
        answer[i] += moves;
        balls += Number(boxes[i]);
        moves += balls;
    }
    moves = balls = 0;
    // Right to left
    for (let i = n - 1; i >= 0; --i) {
        answer[i] += moves;
        balls += Number(boxes[i]);
        moves += balls;
    }
    return answer;
};
      

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n²) because for each box, we check every other box.
  • Space Complexity: O(n) for the answer array.
• Optimized approach (two-pass):
  • Time Complexity: O(n) since each pass (left-to-right and right-to-left) is linear.
  • Space Complexity: O(n) for the answer array, with only O(1) extra variables.

The optimized approach is much better for large inputs, as it avoids unnecessary repeated calculations.

Summary

The key insight in this problem is that the total movement cost for each box can be efficiently computed using two linear passes: one from the left and one from the right. By accumulating the number of balls and their movement costs as we go, we avoid the inefficiency of the brute-force approach and achieve an elegant O(n) solution.

This technique of using prefix and suffix accumulations is a powerful tool for similar problems where costs or counts need to be aggregated from both directions.