Prefix and Suffix Sum | Easy to understand with Diagram | Beats 100% of Python | Java
IntuitionThe problem requires calculating the minimum number of operations needed to move all balls to each box. Instead of moving balls one by one for each box
# Intuition
The problem requires calculating the minimum number of operations needed to move all balls to each box. Instead of moving balls one by one for each box (which is computationally expensive), we can use the prefix-suffix approach to calculate the required operations efficiently.

- Prefix Array: Keeps track of the operations needed to move balls from the left side of the current box.
- Suffix Array: Keeps track of the operations needed to move balls from the right side of the current box.
Combining the two arrays for each box gives the total operations.

# Approach
## 1. Initialization:

- Convert the input string boxes into a list for easier manipulation.
- Create two arrays, prefix and suffix, initialized to zeros. These arrays store the left-to-right and right-to-left cumulative operations, respectively.
- Track the number of balls encountered during sweeps (balls).

## 2. Left-to-Right Sweep:

- Start from the leftmost box.
- Use the prefix array to accumulate operations needed to move balls from the left to each box.

## 3. Right-to-Left Sweep:

- Start from the rightmost box.
- Use the suffix array to accumulate operations needed to move balls from the right to each box.

## 4. Combine Results:

- For each box, the total operations are the sum of the corresponding values from the prefix and suffix arrays.

## 5. Return the Result:

- Return the final array res, which stores the minimum operations for each box.

# Complexity
- Time complexity:
$$O(n)$$

- Space complexity:
$$O(n)$$

# Code
```python3 []
class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        boxes = list(boxes)
        prefix = [0]*len(boxes)
        balls = int(boxes[0])
        for i in range(1,len(boxes)):
            prefix[i] = prefix[i-1]+balls
            balls += int(boxes[i])
        balls = int(boxes[-1])
        suffix = [0]*len(boxes)
        for i in range(len(boxes)-2,-1,-1):
            suffix[i] = suffix[i+1]+balls
            balls += int(boxes[i])
        res = [0]*len(boxes)
        for i in range(len(res)):
            res[i] = prefix[i]+suffix[i]
        return res

```
```java []
class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        char[] boxArray = boxes.toCharArray();
        int[] prefix = new int[n];
        int balls = boxArray[0] - '0'; 
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + balls;
            balls += boxArray[i] - '0'; 
        }
        int[] suffix = new int[n];
        balls = boxArray[n - 1] - '0'; 
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = suffix[i + 1] + balls;
            balls += boxArray[i] - '0'; 
        }
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = prefix[i] + suffix[i];
        }      
        return res;
    }
}


```
['Array', 'String', 'Suffix Array', 'Prefix Sum', 'Java', 'Python3']