Beats 100% Prefix | Suffix Array Detailed Explanation 
🧠 Problem Understanding and IntuitionThe problem is about calculating the minimum number of operations needed to move all balls to each box in a binary string,
# 🧠 Problem Understanding and Intuition

The problem is about calculating the minimum number of operations needed to move all balls to each box in a binary string, where:
- `1` indicates the presence of a ball in the box.
- `0` indicates the box is empty.

### 🔑 Key Insight: 

Instead of calculating the operations naively for every box (which would result in $$O(n^2)$$ time complexity), we can optimize by:
1. Splitting the calculation into **prefix traversal** (left-to-right) and **suffix traversal** (right-to-left).
2. Using cumulative counts and distances to compute the result in $$O(n)$$ time.
---
## video solution ##
https://youtu.be/huBkgsnloVo

7 jan solution https://leetcode.com/problems/string-matching-in-an-array/solutions/6241804/simple-for-loop-detailed-explation/?envType=daily-question&envId=2025-01-07

---

# Approach

### Key Idea:
We can calculate the minimum operations for each box by summing:
1. **Operations to move balls from the left side (prefix traversal)**.
2. **Operations to move balls from the right side (suffix traversal)**.

### Steps:
1. **Initialize Variables:**
   - A `distances` array to store the result for each box.
   - Two sets of counters:
     - `prefixCount` and `prefixSum` for the left-to-right traversal.
     - `suffixCount` and `suffixSum` for the right-to-left traversal.

2. **Prefix Traversal (Left to Right):**
   - Traverse the string from left to right.
   - Maintain `prefixCount` (number of balls encountered so far) and `prefixSum` (total operations for all balls encountered so far).
   - For each box:
     - Calculate the operations needed to bring all balls to this box based on `prefixCount` and `prefixSum`.
The prefix formula calculates the minimum number of moves to bring all balls to box `i`. 
It uses the formula: `distances[i] = prefixCount * i - prefixSum`.
- `prefixCount` counts how many balls are to the left of box `i`.
- `prefixSum` accumulates the sum of the indices of boxes with balls to the left of `i`.
This formula efficiently computes the result by considering how far each ball needs to move.


3. **Suffix Traversal (Right to Left):**
   - Traverse the string from right to left.
   - Maintain `suffixCount` (number of balls encountered so far) and `suffixSum` (total operations for all balls encountered so far).
   - For each box:
     - Add the operations needed to bring all balls from the right to this box.

4. **Combine Results:**
   - The total operations for each box are the sum of operations from the prefix and suffix traversals.

---

# Complexity
- **Time complexity:**  
  $$O(n)$$  
  - We perform two linear traversals of the string.

- **Space complexity:**  
  $$O(n)$$  
  - We use an auxiliary array (`distances`) to store the results.

---

# Example Walkthrough

### Input:
`boxes = "110"`

---

### Prefix Traversal:

| Index | `prefixCount` | `prefixSum` | Operations at Index | Explanation                            |
|-------|---------------|-------------|----------------------|----------------------------------------|
|   0   |       0       |      0      |          0           | No balls encountered yet.              |
|   1   |       1       |      0      |          1           | One ball encountered at index 0.       |
|   2   |       2       |      1      |          3           | Two balls: one from index 0, one from 1.|

Result after prefix traversal: `[0, 1, 3]`.

---

### Suffix Traversal:

| Index | `suffixCount` | `suffixSum` | Operations at Index | Explanation                            |
|-------|---------------|-------------|----------------------|----------------------------------------|
|   2   |       0       |      0      |          0           | No balls encountered yet.              |
|   1   |       0       |      0      |          0           |No       |
|   0   |       1       |      1      |          1           | One balls: one from index 1|

Result after suffix traversal: `[1, 0, 0]`.

---

### Combine Results:

| Index | Prefix Operations | Suffix Operations | Total Operations |
|-------|-------------------|-------------------|------------------|
|   0   |         0         |         1         |        1         |
|   1   |         1         |         0         |        1         |
|   2   |         3         |         0         |        3         |

Final result: `[1, 2, 3]`.

---
![9c6f9412-c860-47d6-9a2e-7fcf37ff3321_1686334926.180891.png](https://assets.leetcode.com/users/images/4fd36174-bc57-4934-9d55-668edee0d743_1736070909.043861.png)

---
## Join For detailed maths formula and intitutive code idea thinking And More Secret Solutions  ## 
 # [Telegram](https://t.me/leetmath) #
### This Method Is New So That Why It is Here ##

```C++ []
class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.size();
        vector<int> left(n, 0), right(n, 0), res(n, 0);
        int count = (boxes.at(0) == '1' ? 1 : 0);

        for (int i = 1; i < n; i++) {
            left[i] = left[i - 1] + count;
            count += (boxes.at(i) == '1' ? 1 : 0);
        }

        count = (boxes.at(n-1) == '1' ? 1 : 0);

        for (int i = n - 2; i >= 0; i--) {
            right[i] = right[i + 1] + count;
            count += (boxes.at(i) == '1' ? 1 : 0);
        }

        for (int i = 0; i < n; i++) {
            res[i] = left[i] + right[i];
        }

        return res;
    }
};
```
### With Formula ###

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

    int prefixCount = 0;  
    int prefixSum = 0;    

    for (int i = 0; i < n; ++i) {
        distances[i] = prefixCount * i - prefixSum;
        if (boxes[i] == '1') {
            ++prefixCount;
            prefixSum += i;
        }
    }

    int suffixCount = 0;  
    int suffixSum = 0;    

    for (int i = n - 1; i >= 0; --i) {
        distances[i] += suffixSum - suffixCount * i;
        if (boxes[i] == '1') {
            ++suffixCount;
            suffixSum += i;
        }
    }

    vector<int> ans;
    for (int dist : distances) {
       ans.push_back(dist);
    }

    return ans;
    }
};
```
```java []
class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] distances = new int[n];

        int prefixCount = 0;
        int prefixSum = 0;

        for (int i = 0; i < n; ++i) {
            distances[i] = prefixCount * i - prefixSum;
            if (boxes.charAt(i) == '1') {
                ++prefixCount;
                prefixSum += i;
            }
        }

        int suffixCount = 0;
        int suffixSum = 0;

        for (int i = n - 1; i >= 0; --i) {
            distances[i] += suffixSum - suffixCount * i;
            if (boxes.charAt(i) == '1') {
                ++suffixCount;
                suffixSum += i;
            }
        }

        return distances;
    }
}
```
```Python3 []
class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        distances = [0] * n

        prefixCount = 0
        prefixSum = 0

        for i in range(n):
            distances[i] = prefixCount * i - prefixSum
            if boxes[i] == '1':
                prefixCount += 1
                prefixSum += i

        suffixCount = 0
        suffixSum = 0

        for i in range(n - 1, -1, -1):
            distances[i] += suffixSum - suffixCount * i
            if boxes[i] == '1':
                suffixCount += 1
                suffixSum += i

        return distances
```
```C []
#include <stdlib.h>
#include <string.h>

int* minOperations(char* boxes, int* returnSize) {
    int n = strlen(boxes);
    int* distances = (int*)malloc(n * sizeof(int));

    int prefixCount = 0;
    int prefixSum = 0;

    // Calculate prefix sums
    for (int i = 0; i < n; ++i) {
        distances[i] = prefixCount * i - prefixSum;
        if (boxes[i] == '1') {
            ++prefixCount;
            prefixSum += i;
        }
    }

    int suffixCount = 0;
    int suffixSum = 0;

    // Calculate suffix sums and update the distances array
    for (int i = n - 1; i >= 0; --i) {
        distances[i] += suffixSum - suffixCount * i;
        if (boxes[i] == '1') {
            ++suffixCount;
            suffixSum += i;
        }
    }

    *returnSize = n;  // Set the size of the result array
    return distances; // Return the dynamically allocated array
}
```
```C# []
public class Solution {
    public int[] MinOperations(string boxes) {
        int n = boxes.Length;
        int[] distances = new int[n];

        int prefixCount = 0;
        int prefixSum = 0;

        // Calculate prefix sums
        for (int i = 0; i < n; ++i) {
            distances[i] = prefixCount * i - prefixSum;
            if (boxes[i] == '1') {
                prefixCount++;
                prefixSum += i;
            }
        }

        int suffixCount = 0;
        int suffixSum = 0;

        // Calculate suffix sums and update the distances array
        for (int i = n - 1; i >= 0; --i) {
            distances[i] += suffixSum - suffixCount * i;
            if (boxes[i] == '1') {
                suffixCount++;
                suffixSum += i;
            }
        }

        return distances;
    }
}
```
```JavaScript []
/**
 * @param {string} boxes
 * @return {number[]}
 */
var minOperations = function(boxes) {
    const n = boxes.length;
    const distances = new Array(n).fill(0);

    let prefixCount = 0;
    let prefixSum = 0;

    // Calculate prefix sums
    for (let i = 0; i < n; i++) {
        distances[i] = prefixCount * i - prefixSum;
        if (boxes[i] === '1') {
            prefixCount++;
            prefixSum += i;
        }
    }

    let suffixCount = 0;
    let suffixSum = 0;

    // Calculate suffix sums and update the distances array
    for (let i = n - 1; i >= 0; i--) {
        distances[i] += suffixSum - suffixCount * i;
        if (boxes[i] === '1') {
            suffixCount++;
            suffixSum += i;
        }
    }

    return distances;
};
```
['Array', 'String', 'C', 'Suffix Array', 'Prefix Sum', 'C++', 'Java', 'Python3', 'JavaScript', 'C#']