Beats 100% | 3 Solutions | Prefix Sum | Array | Solution for LeetCode#1769
IntuitionThe problem requires calculating the minimum number of operations needed to move all balls to each box. A straightforward approach would be to calculat
![image.png](https://assets.leetcode.com/users/images/1fbf9c94-0758-4dc5-a609-0b7b1b7173fc_1736129613.3900979.png)

# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem requires calculating the minimum number of operations needed to move all balls to each box. A straightforward approach would be to calculate this for each box separately, but that would be inefficient. Instead, we can use a two-pass approach to calculate cumulative operations from left to right and right to left.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Convert the input string to an integer array for easier manipulation.
2. Create two arrays, left and right, to store cumulative operations.
3. Perform a left-to-right pass:
	- Count the number of '1's encountered.
	- For each position, calculate cumulative operations from the left.
4. Perform a right-to-left pass:
	- Count the number of '1's encountered.
	- For each position, calculate cumulative operations from the right.
5. Sum the left and right arrays to get the total operations for each position.

# Complexity
- Time complexity: O(n), One pass for left array, one pass for right array, and one final pass to sum them
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(n), Space for arrBox, left, and right arrays
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code Option-01
```java []
class Solution {
    public int[] minOperations(String boxes) {
        int n=boxes.length();
        
        int[] arrBox=new int[n];
        for(int i=0; i<n; i++){
            arrBox[i]=boxes.charAt(i)-'0';
        }

        int[] left=new int[n]; 
        int[] right=new int[n]; 

        int oneCnt=0;
        // Left to right pass moving count
        oneCnt=arrBox[0];
        for(int i=1; i<n; i++){
            left[i]=left[i-1]+oneCnt;
            oneCnt+=arrBox[i];
        }

        // Right to left pass moving count  
        oneCnt=arrBox[n-1];
        for(int i=n-2; i>=0; i--){
            right[i]=right[i+1]+oneCnt;
            oneCnt+=arrBox[i];
        }

        // Sum the left and right 
        for(int i=0; i<n; i++){
            arrBox[i]=left[i]+right[i];
        }        

        return arrBox;
    }
}
```

# Code Option-02: Array "left", "right" removed
```java []
class Solution {
    public int[] minOperations(String boxes) {
        int n=boxes.length();
        
        int[] arrBox=new int[n];
        for(int i=0; i<n; i++){
            arrBox[i]=boxes.charAt(i)-'0';
        }

        int[] res=new int[n]; 

        int oneCnt=0, cumSum=0;
        // Left to right pass moving count
        for(int i=0; i<n; i++){
            res[i]+=cumSum;
            oneCnt+=arrBox[i];
            cumSum+=oneCnt;
        }

        oneCnt=0; cumSum=0;
        // Right to left pass moving count          
        for(int i=n-1; i>=0; i--){
            res[i]+=cumSum;
            oneCnt+=arrBox[i];
            cumSum+=oneCnt;
        }


        return res;
    }
}
```

# Code Option-03: Only one loop(while) is used
```java []
class Solution {
    public int[] minOperations(String boxes) {
        int n=boxes.length();
        
        int[] arrBox=new int[n];
        for(int i=0; i<n; i++){
            arrBox[i]=boxes.charAt(i)-'0';
        }

        int[] res=new int[n]; 

        int oneCntL=0, cumSumL=0;
        int oneCntR=0, cumSumR=0;
        int i=0, j=n-1;
        while(i<n && j>=0){
            // Left to right pass moving count
            res[i]+=cumSumL;
            oneCntL+=arrBox[i];
            cumSumL+=oneCntL;
            i++;

            // Right to left pass moving count    
            res[j]+=cumSumR;
            oneCntR+=arrBox[j];
            cumSumR+=oneCntR;
            j--;
        }


        return res;
    }
}
```
['Prefix Sum', 'Java']