Minimum Operations to Gather All Balls: Beats 100%! 🚀
Minimum Operations to Gather All Balls: Beats 100%! 🚀📦 Problem OverviewYou have n boxes represented as a binary string where:
'1' = box contains a ball
'0' = bo
# **Minimum Operations to Gather All Balls: Beats 100%! 🚀**

## 📦 Problem Overview  
You have `n` boxes represented as a binary string where:  
- `'1'` = box contains a ball  
- `'0'` = box is empty  

Your goal is to calculate the **minimum number of operations** needed to move all balls to each box. Operations allow moving one ball to an adjacent box.  

---

## 🛠 Optimized Approach (Prefix & Postfix Sums)  

### 🔑 Key Insight:  
To avoid a brute-force `O(n²)` solution, we leverage **prefix** and **postfix sums** to precompute distances efficiently in linear time.  

---

### **Steps to Solve**  

1️⃣ **Prefix Array:**  
- Traverse from **left to right**, accumulating the total operations required to move balls from previous boxes.  
- Track the count of balls encountered so far (`pre`).  

2️⃣ **Postfix Array:**  
- Traverse from **right to left**, accumulating the total operations needed for balls from succeeding boxes.  
- Track the count of balls encountered in reverse (`post`).  

3️⃣ **Combine Results:**  
- Sum the values from both prefix and postfix arrays for each index to get the final result.  

---

## 📈 Complexity Analysis  

- **Time Complexity:**  
  $$O(n)$$ for computing prefix and postfix arrays in two passes.  

- **Space Complexity:**  
  $$O(n)$$ for storing prefix and postfix arrays.  

---

## 🔍 Example Walkthrough  

### **Input:**  
`boxes = "110"`

### **Steps:**  
1. **Prefix Array Calculation:**  
   - Start from the left, accumulate distances and update the ball count (`pre`):  
     - Box 0: `0`  
     - Box 1: `1`  
     - Box 2: `3`  
   - **Prefix = [0, 1, 3]**

2. **Postfix Array Calculation:**  
   - Start from the right, accumulate distances and update the ball count (`post`):  
     - Box 2: `0`  
     - Box 1: `1`  
     - Box 0: `1`  
   - **Postfix = [1, 1, 0]**

3. **Combine Results:**  
   - Result = Prefix + Postfix = `[1, 1, 3]`  

---

## **Final Output:**  
### **Result = [1, 1, 3]**  

This approach ensures optimal performance while maintaining clarity!


# Code
```python3 []
class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        prefix, postfix = [], []
        pre = post = now = 0

        # Calculate prefix costs (left to right)
        for x in boxes:
            now += pre
            prefix.append(now)
            if x == "1":
                pre += 1

        now = 0
        # Calculate postfix costs (right to left)
        for x in boxes[::-1]:
            now += post
            postfix.append(now)
            if x == "1":
                post += 1

        # Combine prefix and postfix
        postfix = postfix[::-1]
        return [postfix[i] + prefix[i] for i in range(len(boxes))]

```
``` cpp []
class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.size();
        vector<int> prefix(n, 0), postfix(n, 0);
        int pre = 0, post = 0, now = 0;

        // Prefix array
        for (int i = 0; i < n; i++) {
            now += pre;
            prefix[i] = now;
            if (boxes[i] == '1') pre++;
        }

        now = 0;
        // Postfix array
        for (int i = n - 1; i >= 0; i--) {
            now += post;
            postfix[i] = now;
            if (boxes[i] == '1') post++;
        }

        // Combine prefix and postfix
        vector<int> result(n);
        for (int i = 0; i < n; i++) {
            result[i] = prefix[i] + postfix[i];
        }
        return result;
    }
};

```
``` java []
class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] prefix = new int[n];
        int[] postfix = new int[n];
        int pre = 0, post = 0, now = 0;

        // Prefix array
        for (int i = 0; i < n; i++) {
            now += pre;
            prefix[i] = now;
            if (boxes.charAt(i) == '1') pre++;
        }

        now = 0;
        // Postfix array
        for (int i = n - 1; i >= 0; i--) {
            now += post;
            postfix[i] = now;
            if (boxes.charAt(i) == '1') post++;
        }

        // Combine prefix and postfix
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = prefix[i] + postfix[i];
        }
        return result;
    }
}

```

``` javascript []
var minOperations = function(boxes) {
    const n = boxes.length;
    const prefix = Array(n).fill(0);
    const postfix = Array(n).fill(0);
    let pre = 0, post = 0, now = 0;

    // Prefix array
    for (let i = 0; i < n; i++) {
        now += pre;
        prefix[i] = now;
        if (boxes[i] === '1') pre++;
    }

    now = 0;
    // Postfix array
    for (let i = n - 1; i >= 0; i--) {
        now += post;
        postfix[i] = now;
        if (boxes[i] === '1') post++;
    }

    // Combine prefix and postfix
    const result = Array(n);
    for (let i = 0; i < n; i++) {
        result[i] = prefix[i] + postfix[i];
    }
    return result;
};
```

``` typescript []
function minOperations(boxes: string): number[] {
    const n = boxes.length;
    const prefix: number[] = new Array(n).fill(0);
    const postfix: number[] = new Array(n).fill(0);
    let pre = 0, post = 0, now = 0;

    // Prefix array
    for (let i = 0; i < n; i++) {
        now += pre;
        prefix[i] = now;
        if (boxes[i] === '1') pre++;
    }

    now = 0;
    // Postfix array
    for (let i = n - 1; i >= 0; i--) {
        now += post;
        postfix[i] = now;
        if (boxes[i] === '1') post++;
    }

    // Combine prefix and postfix
    const result: number[] = new Array(n);
    for (let i = 0; i < n; i++) {
        result[i] = prefix[i] + postfix[i];
    }
    return result;
}

```




















['Array', 'String', 'C', 'Prefix Sum', 'Python', 'C++', 'Java', 'Python3', 'JavaScript', 'C#']