EASY C++ O(N) SOLUTION IN 2 PASS
The idea here is to use use Prefix sum array. \nWe iterate the given array twice, but in opposite direction. In 1st pass we move from left to right, storing the
The idea here is to use use Prefix sum array. \nWe iterate the given array twice, but in opposite direction. In 1st pass we move from left to right, storing the total balls to be moved from 0th index to current ith index (ie. all elements to left), in a variable (here sum) and res stores the operations needed to move all balls to ith index. Thus, res[i]= res[i-1]+ sum, gives minimum number of operations needed to move all balls from the left indices.\n\nSimilarily, we need to iterate from right to left and storing total balls in a variable (sum) and using it to find res[i], which is res[i]=res[i-1]+sum.\n\n**Time Complexity** :  O(N) due to the linear traversal from 1st element to last element & vice versa\n**Space Complexity:** O(N) due to the space used to store the prefix sum and ultimately the result.\n```\nvector<int> minOperations(string boxes) {\n        int n=boxes.length();\n        vector<int>res(n);\n        int last_cost=0, sum=boxes[0]-\'0\';\n        for(int i=1;i<n;i++){\n            res[i]+=sum+last_cost;\n            last_cost=res[i];\n            sum+=(boxes[i]-\'0\');\n        }\n        \n        last_cost=0,sum=boxes[n-1]-\'0\';\n        \n        for(int i=n-2;i>=0;i--){\n            res[i]+=sum+last_cost;\n            last_cost=(sum+last_cost);\n            sum+=(boxes[i]-\'0\');\n        }\n        return res;\n    }\n\n```
['C', 'Prefix Sum']