0ms | Beats 100.00% | Efficient , Easy & Simple C++ Solution | Full Explained With Example | Proof
IntuitionTo calculate the total moves efficiently:
Left Moves: We keep track of the number of balls we've encountered so far (ballsToLeft) while moving left-to-
![Screenshot (27).png](https://assets.leetcode.com/users/images/5d1cce38-a728-4797-bc85-588b51612676_1736124411.0200872.png)

# Intuition
To calculate the total moves efficiently:

- Left Moves: We keep track of the number of balls we've encountered so far (ballsToLeft) while moving left-to-right. As we move forward, the distance for each ball increases, and we accumulate the total moves in movesToLeft.
- Right Moves: Similarly, we calculate moves in the reverse direction (right-to-left) by maintaining a ballsToRight count and a movesToRight value.

By combining these calculations in a single loop:
- We add the movesToLeft to the result during the left-to-right traversal.
- We add the movesToRight during the right-to-left traversal.

This ensures we efficiently calculate the total moves required for balls to reach each box.
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
1.  Initialization:

- Let n be the length of the boxes string.
- Create an array answer of size n to store the results.
- Initialize:
> ballsToLeft and movesToLeft for the left-to-right calculation.
ballsToRight and movesToRight for the right-to-left calculation.

2. Single Pass:

- Loop through the string boxes:
- For the Left Pass:
> Add the current movesToLeft to the corresponding index in answer.
Update ballsToLeft by adding the count of balls at the current box.
Increment movesToLeft by the current ballsToLeft to account for the next box.
- For the Right Pass:
> Calculate the index j for the reverse direction as n - 1 - i.
Add the current movesToRight to the corresponding index in answer.
Update ballsToRight similarly.
Increment movesToRight for the next box.
Return Result:

The answer array contains the total moves for all balls to reach each box.


# **Example :**
Input:
boxes = "110"

Calculation:
1. Left Pass:

- At index 0:
> ballsToLeft = 1, movesToLeft = 0.
Add movesToLeft to answer[0].

- At index 1:
> ballsToLeft = 2, movesToLeft = 1.
Add movesToLeft to answer[1].

- At index 2:
> ballsToLeft = 2, movesToLeft = 3.
Add $$movesToLeft$$ to answer[2].

2. Right Pass:

- At index 2:
> ballsToRight = 0, movesToRight = 0.
Add movesToRight to answer[2].

- At index 1:
> ballsToRight = 1, movesToRight = 1.
Add movesToRight to answer[1].

- At index 0:
> ballsToRight = 2, movesToRight = 3.
Add movesToRight to answer[0].

Output:
[1, 1, 3]
<!-- Describe your approach to solving the problem. -->

# Complexity
Let 𝑛 be the length of the string boxes.
- Time complexity: 𝑂(𝑛)

The algorithm processes the string boxes in a single loop. During this loop, operations like accessing characters, updating variables, and modifying the answer array are performed, each taking constant time. Since the loop runs exactly 𝑛 times, the total time complexity is 𝑂(𝑛)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: 𝑂(1)

The algorithm uses a few integer variables (ballsToLeft, movesToLeft, ballsToRight, movesToRight) to track the calculations for left and right passes. These variables require constant space regardless of the input size. The answer array is excluded from the space complexity analysis because it is part of the required output. Therefore, the algorithm's space complexity is 𝑂(1).
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.size();
        vector<int> answer(n, 0);

        int ballsToLeft = 0, movesToLeft = 0;
        int ballsToRight = 0, movesToRight = 0;

        // Single pass: calculate moves from both left and right
        for (int i = 0; i < n; i++) {
            // Left pass
            answer[i] += movesToLeft;
            ballsToLeft += boxes[i] - '0';
            movesToLeft += ballsToLeft;

            // Right pass
            int j = n - 1 - i;
            answer[j] += movesToRight;
            ballsToRight += boxes[j] - '0';
            movesToRight += ballsToRight;
        }

        return answer;
    }
};
```
['Array', 'Hash Table', 'Two Pointers', 'String', 'Binary Search', 'Greedy', 'Recursion', 'String Matching', 'Prefix Sum', 'C++']