Minimum Number of Operations to Move All Balls to Each Box

Prefix Sum might just be the name of the game.

My algorithm stems from the fact that each answer[i] is related to answer[i-1] and answer[i+1] (if they exist). What I mean by this, is that, since each answer[i] is related towards the relative position of each ball and the relative position of each ball does not change, when we iterate through each answer[i], we find that we can calculate answer[i+1] using our answers from the previous index answer[i].

For example, our answer[i] value depends on the n balls that we have passed, and the m balls that we have not passed yet. When we calcualte answer[i+1], we find that it is simply just answer[i] + n - m (as each of the n balls gets 1 box further, and each of the m balls gets 1 box closer).

Using this logic, we can just iterate through the boxes string to find our answer for answer[0], and use it to calculate the rest of the values inside answer.

code

class Solution {
public:
    vector<int> minOperations(string boxes) {
        int balls = 0;
        vector<int> ans;
        int curr = 0;
        for (int i = 0; i < boxes.size(); ++i) {
            balls += boxes[i]-'0';
            curr += (boxes[i]-'0')*i;
        }
        int passed = 0;
        ans.push_back(curr);
        passed += boxes[0]-'0';
        for (int i = 1; i < boxes.size(); ++i) {
            curr += passed;
            curr -= balls-passed;
            ans.push_back(curr);
            passed += boxes[i]-'0';
        }
        return ans;
    }
};

complexity

• Time: O(n)
• Space: O(n)