C++ | EXPLAINED | LTR + RTL | O(n)
\n\n/*\n\nHarshit Gupta | 10th July, 2021\n--------------------------------\n\nMinimum Number of Operations to Move All Balls to Each Box\n\nYou have n boxes. Y
```\n\n/*\n\nHarshit Gupta | 10th July, 2021\n--------------------------------\n\nMinimum Number of Operations to Move All Balls to Each Box\n\nYou have n boxes. You are given a binary string boxes of length n, where boxes[i] is \'0\' if the ith box is empty, \n    and \'1\' if it contains one ball.\nIn one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1. \n    Note that after doing so, there may be more than one ball in some boxes.\nReturn an array answer of size n, where answer[i] is the minimum number of operations needed to move all the balls \n    to the ith box.\n\nEach answer[i] is calculated considering the initial state of the boxes.\n\nExample 1:\n    Input: boxes = "110"\n    Output: [1,1,3]\n    Explanation: The answer for each box is as follows:\n    1) First box: you will have to move one ball from the second box to the first box in one operation.\n    2) Second box: you will have to move one ball from the first box to the second box in one operation.\n    3) Third box: you will have to move one ball from the first box to the third box in two operations, \n        and move one ball from the second box to the third box in one operation.\n\nExample 2:\n    Input: boxes = "001011"\n    Output: [11,8,5,4,3,4]\n\nhttps://leetcode.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/\n------\n\nSolution: For each element in the array, we have to find the distance with all the 1s in the array.\n\n    1. Brute Force:\n        For each element in the array, check for all 1s in the array and add the dist of all 1s.\n\n        TC: O(n2)\n        SC: O(1)\n\n    2. LeftToRight + RightToLeft Traversal:\n        - For each element, calculate the number of 1s on its left and 1s on its right\n        - For each element, calculate the cost of 1s from the elements on its left & similarly calcualate cost \n            of 1s from the elements on its right\n        - Add the leftCost & rightCost for each i\n    \n        Example:\n        boxes      11010\n        leftCount  01223 (How many 1s are to the left of your index)\n        leftCost   01358 (What is the cost of 1s to the left of your index)\n        rightCount 21100 (How many 1s are to the right of your index)\n        rightCost  42100 (What is the cost of 1s to the right of your index)\n        ans        43458 (Total cost of 1s to the left + right)\n\n        TC: O(n)\n        SC: O(n)\n\nParadigm:\n---\n  NOTE: \n\n*/\n\n\nclass Solution {\npublic:\n    vector<int> minOperations(string boxes) {\n        int n = boxes.size();\n        vector<int> leftCost(n), leftCount(n);\n        vector<int> rightCost(n), rightCount(n);\n        vector<int> res;\n        \n        for(int i=1; i<n; i++){\n            if(boxes[i-1] == \'1\')\n                leftCount[i] = leftCount[i-1]+1;\n            else \n                leftCount[i] = leftCount[i-1];\n            leftCost[i] = leftCost[i-1]+leftCount[i];\n        }\n        \n        for(int i=n-2; i>=0; i--){\n            if(boxes[i+1] == \'1\')\n                rightCount[i] = rightCount[i+1]+1;\n            else \n                rightCount[i] = rightCount[i+1];\n            rightCost[i] = rightCost[i+1]+rightCount[i];\n        }\n        \n        for(int i=0; i<n; i++){\n            res.push_back(leftCost[i]+rightCost[i]);\n        }\n        \n        return res;\n    }\n};\n```
['C', 'C++']