Minimum Number of Operations to Move All Balls to Each Box

Leetcode Problem:

• Minimum Number of Operations to Move All Balls to Each Box

Summary

• Given a binary string representing boxes with balls, find the minimum number of operations needed to move all the balls to each box.

Approach

• The approach is to first count the number of balls in each box and store it in the `ltor` and `rtol` arrays
• Then, calculate the minimum number of operations needed to move all the balls to each box by adding the `ltor` and `rtol` values at each index.

Complexity

• O(n), where n is the length of the binary string.

Explanation

• The provided C++ solution uses two arrays, `ltor` and `rtol`, to store the cumulative count of balls from the left and right sides of each box
• The minimum number of operations needed to move all the balls to each box is calculated by adding the `ltor` and `rtol` values at each index
• This approach ensures that the minimum number of operations is calculated considering the initial state of the boxes.

Solution Code:

class Solution {
public:
    int ltor[2000];
    int rtol[2000];
    vector minOperations(string boxes) {
        vector ans;
        int oneCnt = 0;
        for(int i = 0 ; i < boxes.size() - 1; i++){
            if(boxes[i] == '1'){
                oneCnt++;
            }
            ltor[i+1] = ltor[i] + oneCnt;
        }
        oneCnt = 0;
        for(int i = boxes.size() - 1; i > 0 ; i--){
            if(boxes[i] == '1'){
                oneCnt++;
            }
            rtol[i-1] = rtol[i] + oneCnt;
        }
        for(int i = 0 ; i < boxes.size(); i++){
            ans.push_back(ltor[i] + rtol[i]);
        }
        return ans;
    }
};