# Minimum Number of Operations to Move All Balls to Each Box
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-operations-to-move-all-balls-to-each-box
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, String
---
## Problem
You have `n` boxes. You are given a binary string `boxes` of length `n`, where `boxes[i]` is `'0'` if the `ith` 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 `ith` box.

Each `answer[i]` is calculated considering the **initial** state of the boxes.

**Example 1:**

**Input:** boxes = "110"
**Output:** [1,1,3]
**Explanation:** The answer for each box is as follows:
1) First box: you will have to move one ball from the second box to the first box in one operation.
2) Second box: you will have to move one ball from the first box to the second box in one operation.
3) Third box: you will have to move one ball from the first box to the third box in two operations, and move one ball from the second box to the third box in one operation.

**Example 2:**

**Input:** boxes = "001011"
**Output:** [11,8,5,4,3,4]

**Constraints:**

* `n == boxes.length`
* `1 <= n <= 2000`
* `boxes[i]` is either `'0'` or `'1'`.

# Approaches
## Brute Force Simulation
This approach directly translates the problem statement into code. For each box, we calculate the cost of moving every ball in the entire set to that specific box. This is done by iterating through all `n` boxes for each of the `n` target boxes.
**Time:** O(n^2), where `n` is the length of the `boxes` string. For each of the `n` boxes, we iterate through all `n` boxes again. · **Space:** O(n) to store the output array. If the output array is not considered extra space, the complexity is O(1).
**Pros:** Very simple and intuitive to understand.; Easy to implement correctly.
**Cons:** The time complexity is quadratic, which can be slow for larger inputs (though it passes within the given constraints).
### Explanation
We create an answer array of the same size as the input string `boxes`. We then use a nested loop structure. The outer loop selects a target box, `i`. The inner loop scans the entire `boxes` string to find the locations of all balls. For each ball found at index `j`, we calculate the number of operations needed to move it to box `i`. Since one operation moves a ball to an adjacent box, the total operations to move a ball from `j` to `i` is simply the absolute difference of their indices, `abs(i - j)`. We sum these costs for all balls for a given target box `i` and store it in `answer[i]`. We repeat this process for all possible target boxes.

```java
class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            int currentOperations = 0;
            for (int j = 0; j < n; j++) {
                if (boxes.charAt(j) == '1') {
                    currentOperations += Math.abs(i - j);
                }
            }
            answer[i] = currentOperations;
        }

        return answer;
    }
}
```
### Algorithm
1. Initialize an integer array `answer` of size `n` with all elements set to 0.
2. Iterate through each target box `i` from `0` to `n-1`.
3. For each `i`, initialize a variable `total_ops = 0`.
4. Start a nested loop, iterating through all boxes `j` from `0` to `n-1`.
5. Inside the nested loop, check if `boxes.charAt(j)` is '1'.
6. If it is, calculate the distance required to move the ball from `j` to `i`, which is `Math.abs(i - j)`.
7. Add this distance to `total_ops`.
8. After the inner loop finishes, assign the accumulated `total_ops` to `answer[i]`.
9. After the outer loop finishes, return the `answer` array.

## Two-Pass Linear Time Approach
A more optimal approach is to use two passes to calculate the costs. The total operations for any box `i` can be seen as the sum of two parts: the cost to move all balls from the left of `i` to `i`, and the cost to move all balls from the right of `i` to `i`. We can calculate these two components for all boxes efficiently in two separate linear passes, one from left-to-right and one from right-to-left.
**Time:** O(n), as we perform two independent passes over the array, each taking linear time. · **Space:** O(n) to store the output array. The extra space used by variables is O(1).
**Pros:** Highly efficient with a linear time complexity.; Uses constant extra space (excluding the output array).
**Cons:** Slightly less intuitive than the brute-force approach, as it requires understanding the relationship between the costs of adjacent boxes.
### Explanation
This approach avoids the redundant calculations of the brute-force method. 

In the first pass (left-to-right), we calculate `left_ops[i]`, the cost to move all balls from indices less than `i` to index `i`. We can observe that `left_ops[i] = left_ops[i-1] + (number of balls to the left of i)`. We can maintain a running count of balls and operations. We iterate from `i = 0` to `n-1`, updating the operations needed based on the number of balls encountered so far, and store this intermediate result in our `answer` array.

In the second pass (right-to-left), we do the same for `right_ops[i]`, the cost to move balls from indices greater than `i`. We iterate from `i = n-1` down to `0`, again keeping a running count of balls and operations. We add this result to the value already in the `answer` array. 

After both passes, `answer[i]` will contain the sum of `left_ops[i]` and `right_ops[i]`, which is the total minimum operations.

```java
class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] answer = new int[n];
        int ballsCount = 0;
        int operations = 0;

        // Pass 1: Left to Right
        // Calculate the cost to move balls from the left to the current box i
        for (int i = 0; i < n; i++) {
            operations += ballsCount;
            answer[i] = operations;
            if (boxes.charAt(i) == '1') {
                ballsCount++;
            }
        }

        // Pass 2: Right to Left
        // Calculate the cost to move balls from the right and add it to the previous result
        ballsCount = 0;
        operations = 0;
        for (int i = n - 1; i >= 0; i--) {
            operations += ballsCount;
            answer[i] += operations;
            if (boxes.charAt(i) == '1') {
                ballsCount++;
            }
        }

        return answer;
    }
}
```
### Algorithm
1. The total operations for a box `i` is the sum of operations to move balls from its left and operations to move balls from its right.
2. **Pass 1 (Left to Right):**
   - Initialize an `answer` array, `ballsCount = 0`, and `operations = 0`.
   - Iterate `i` from `0` to `n-1`.
   - For each `i`, all `ballsCount` balls seen so far are now one step further. So, add `ballsCount` to `operations`.
   - Set `answer[i] = operations`.
   - If `boxes.charAt(i)` is '1', increment `ballsCount`.
3. **Pass 2 (Right to Left):**
   - Reset `ballsCount = 0` and `operations = 0`.
   - Iterate `i` from `n-1` down to `0`.
   - Similar to the first pass, add `ballsCount` to `operations`.
   - Add this `operations` value to the existing `answer[i]` (i.e., `answer[i] += operations`).
   - If `boxes.charAt(i)` is '1', increment `ballsCount`.
4. Return the `answer` array.

# Solutions
### Java

```java
class Solution {
public
  int[] minOperations(String boxes) {
    int n = boxes.length();
    int[] left = new int[n];
    int[] right = new int[n];
    for (int i = 1, cnt = 0; i < n; ++i) {
      if (boxes.charAt(i - 1) == '1') {
        ++cnt;
      }
      left[i] = left[i - 1] + cnt;
    }
    for (int i = n - 2, cnt = 0; i >= 0; --i) {
      if (boxes.charAt(i + 1) == '1') {
        ++cnt;
      }
      right[i] = right[i + 1] + cnt;
    }
    int[] ans = new int[n];
    for (int i = 0; i < n; ++i) {
      ans[i] = left[i] + right[i];
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> minOperations(string boxes) {
    int n = boxes.size();
    int left[n];
    int right[n];
    memset(left, 0, sizeof left);
    memset(right, 0, sizeof right);
    for (int i = 1, cnt = 0; i < n; ++i) {
      cnt += boxes[i - 1] == '1';
      left[i] = left[i - 1] + cnt;
    }
    for (int i = n - 2, cnt = 0; ~i; --i) {
      cnt += boxes[i + 1] == '1';
      right[i] = right[i + 1] + cnt;
    }
    vector<int> ans(n);
    for (int i = 0; i < n; ++i)
      ans[i] = left[i] + right[i];
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minOperations(self, boxes: str) -> List[int]: n = len(boxes) left = [0] * n right = [0] * n cnt = 0 for i in range(1, n): if boxes[i - 1] == '1': cnt += 1 left[i] = left[i - 1] + cnt cnt = 0 for i in range(n - 2, - 1, - 1): if boxes[i + 1] == '1': cnt += 1 right[i] = right[i + 1] + cnt return [a + b for a, b in zip(left, right)]

```