Beats 100% | 2 - Approach | JAVA | Well Explained
IntuitionThe problem involves calculating the minimum number of operations to move all the balls to each box. My initial thought was to calculate the distance b
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem involves calculating the minimum number of operations to move all the balls to each box. My initial thought was to calculate the distance between every pair of boxes containing a ball and sum them up for each target box.

# Approach 1: *Brute Force Approach*
<!-- Describe your approach to solving the problem. -->
Iterate through each box, and for each target box, calculate the total moves required to bring all the balls to that box by summing the distances between the current box and all other boxes with balls.
# Complexity
- Time complexity:
        $$O(N^2)$$

- Space complexity:
  $$O(1)$$
---
Here's the code for bruteForce Approach in different languages:

---

# Code
```java []
class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = 0; j < n; j++) {
                if (boxes.charAt(j) == '1') {
                    sum += Math.abs(j - i);
                }
            }
            ans[i] = sum;
        }
        return ans;
    }
}


```
```C++ []
class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.size();
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = 0; j < n; j++) {
                if (boxes[j] == '1') {
                    sum += abs(j - i);
                }
            }
            ans[i] = sum;
        }
        return ans;
    }
};


```
```Python []
class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        ans = [0] * n
        for i in range(n):
            sum_ = 0
            for j in range(n):
                if boxes[j] == '1':
                    sum_ += abs(j - i)
            ans[i] = sum_
        return ans


```
```JavaScript []
var minOperations = function(boxes) {
    let n = boxes.length;
    let ans = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        let sum = 0;
        for (let j = 0; j < n; j++) {
            if (boxes[j] === '1') {
                sum += Math.abs(j - i);
            }
        }
        ans[i] = sum;
    }
    return ans;
};


```
# Approach 2: *Optimal Approach*
<!-- Describe your approach to solving the problem. -->
Use a prefix sum approach to optimize the calculation. Maintain running totals for the moves required from both the left and right sides. This avoids recalculating distances for each target box.

Here's a step by step breakdown of the approach :
- `n` → Length of the binary string.
- `ans` → Array to store the result.
- `sum` → Tracks the total moves required by all the balls on the right - side of the current box to reach to the current box.
- `prefixSum` → Tracks the total moves required by all the balls on the left - side of the current box to reach to the current box.
- `rightBall` → Counts the number of balls to the right of the current box.
- `leftBall` → Counts the number of balls to the left of the current box.

#### Steps :
1. **Initialize Variables:**  
   - `sum` (total moves for right-side balls), `rightBall` (count of right-side balls), and `leftBall` (count of left-side balls).  
   - Pre-compute `sum` and `rightBall` by iterating through the string once.

2. **First Pass (Left to Right):**  
   - Compute total moves required for each box using `sum` and `prefixSum` (moves from the left).  
   - Update the result array `ans[i]`.

3. **Update State:**  
   - If the current box contains a ball, increment `leftBall` and decrement `rightBall`.  
   - Adjust `sum` by subtracting `rightBall` and increment `prefixSum` by adding `leftBall`.

4. **Continue to Next Box:**  
   - Repeat the above for all boxes in one pass.

5. **Return Result:**  
   - The array `ans` now contains the minimum operations required for each box in **O(n)** time.
# Complexity
- Time complexity:
        $$O(N)$$

- Space complexity:
  $$O(1)$$
---
Here's the code for Optimal Approach in different languages:

---

# Code
```java []
class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] ans = new int[n];
        int sum = 0, rightBall = 0, leftBall = 0;

        for (int i = 0; i < n; i++) {
            if (boxes.charAt(i) == '1') {
                sum += i;
                rightBall++;
            }
        }

        int prefixSum = 0;
        for (int i = 0; i < n; i++) {
            ans[i] = sum + prefixSum;
            if (boxes.charAt(i) == '1') {
                leftBall++;
                rightBall--;
            }
            sum -= rightBall;
            prefixSum += leftBall;
        }
        return ans;
    }
}

```
```C++ []
class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.size();
        vector<int> ans(n);
        int sum = 0, rightBall = 0, leftBall = 0;

        for (int i = 0; i < n; i++) {
            if (boxes[i] == '1') {
                sum += i;
                rightBall++;
            }
        }

        int prefixSum = 0;
        for (int i = 0; i < n; i++) {
            ans[i] = sum + prefixSum;
            if (boxes[i] == '1') {
                leftBall++;
                rightBall--;
            }
            sum -= rightBall;
            prefixSum += leftBall;
        }
        return ans;
    }
};

```
```Python []
class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        ans = [0] * n
        sum_ = rightBall = leftBall = 0

        for i in range(n):
            if boxes[i] == '1':
                sum_ += i
                rightBall += 1

        prefixSum = 0
        for i in range(n):
            ans[i] = sum_ + prefixSum
            if boxes[i] == '1':
                leftBall += 1
                rightBall -= 1
            sum_ -= rightBall
            prefixSum += leftBall

        return ans

```
```JavaScript []
var minOperations = function(boxes) {
    let n = boxes.length;
    let ans = new Array(n).fill(0);
    let sum = 0, rightBall = 0, leftBall = 0;

    for (let i = 0; i < n; i++) {
        if (boxes[i] === '1') {
            sum += i;
            rightBall++;
        }
    }

    let prefixSum = 0;
    for (let i = 0; i < n; i++) {
        ans[i] = sum + prefixSum;
        if (boxes[i] === '1') {
            leftBall++;
            rightBall--;
        }
        sum -= rightBall;
        prefixSum += leftBall;
    }

    return ans;
};

```

![upvote.png](https://assets.leetcode.com/users/images/b82d183c-e7f6-4b25-8ff3-06904ee9ba52_1736163040.467357.png)

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