✨100% || C++ || Python || Prefix & Suffix Sums ||🥂Beginner-Friendly
IntuitionThe problem involves determining the number of operations needed to move all balls in boxes to each position. The operations are defined by the number
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem involves determining the number of operations needed to move all balls in boxes to each position. The operations are defined by the number of steps needed to move a ball from one box to another. The goal is to compute this efficiently.
# Approach
<!-- Describe your approach to solving the problem. -->
## Approach 1: Prefix and Suffix Sums

### Initialization:
1. Initialize res vector to store the result for each box.

2. Use variables to keep track of the count of balls and the cumulative sum of steps.

### First Pass (Left to Right):

1. Iterate through the boxes string.

2. For each box, update the result by adding the number of balls and the cumulative sum of steps.

3. Update the count of balls and the cumulative sum.

### Second Pass (Right to Left):

1. Iterate through the boxes string from the end.

2. For each box, update the result similarly, taking into account the balls and steps from the right side.

## Approach 2: Direct Calculation (Not Efficient)

### Index List:
Create a list of indices where the boxes contain balls ('1').

### Calculation:

For each box, calculate the number of steps required to move balls from all other boxes containing balls.

# Complexity
- Time complexity:
    - Approach 1: $$O(n)$$, where 𝑛 is the length of the boxes string.
    - Approach 2: $$O(n \times m)$$, where 𝑛 is the length of the boxes string, and 𝑚 is the number of boxes containing balls.  
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
    - Approach 1: $$O(n)$$ for the result vector.
    - Approach 2: $$O(n + m)$$ for the result vector and index list.
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
### Approach 1
```cpp []
class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n=boxes.length();
        vector<int>res(n);
        int c=0,s=boxes[0]-'0';
        for(int i=1;i<n;i++){
            res[i]+=s+c;
            c=res[i];
            s+=(boxes[i]-'0');
        }
        c=0,s=boxes[n-1]-'0';
        for(int i=n-2;i>=0;i--){
            res[i]+=s+c;
            c=(s+c);
            s+=(boxes[i]-'0');
        }
        return res;
    }
};
```
```python []
class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        res = [0] * n
        c = 0
        s = int(boxes[0])

        for i in range(1, n):
            res[i] += s + c
            c = res[i]
            s += int(boxes[i])
        
        c = 0
        s = int(boxes[n - 1])
        
        for i in range(n - 2, -1, -1):
            res[i] += s + c
            c = s + c
            s += int(boxes[i])
        
        return res
```
### Approach 2
```cpp []
class Solution {
public:
    vector<int> minOperations(string boxes) {
        vector<int>ind;
        int n=boxes.length();
        for(int i=0;i<n;i++){
            if(boxes[i]=='1')
                ind.push_back(i);
        }
        vector<int>res(n,0);
        for(int i=0;i<n;i++){
            for(int j=0;j<ind.size();j++){
                res[i]+=abs(i-ind[j]);
            }
        }
        return res;
    }
};
```
```python []
from typing import List

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        ind = []
        n = len(boxes)
        
        for i in range(n):
            if boxes[i] == '1':
                ind.append(i)
        
        res = [0] * n
        
        for i in range(n):
            for j in range(len(ind)):
                res[i] += abs(i - ind[j])
        
        return res
```
['Array', 'String', 'Prefix Sum', 'C++', 'Python3']