# All Divisions With the Highest Score of a Binary Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/all-divisions-with-the-highest-score-of-a-binary-array)
Canonical: https://scaleengineer.com/dsa/problems/all-divisions-with-the-highest-score-of-a-binary-array
**Data structures:** Array
---
## Problem
You are given a **0-indexed** binary array `nums` of length `n`. `nums` can be divided at index `i` (where `0 <= i <= n)` into two arrays (possibly empty) `numsleft` and `numsright`:

* `numsleft` has all the elements of `nums` between index `0` and `i - 1` **(inclusive)**, while `numsright` has all the elements of nums between index `i` and `n - 1` **(inclusive)**.
* If `i == 0`, `numsleft` is **empty**, while `numsright` has all the elements of `nums`.
* If `i == n`, `numsleft` has all the elements of nums, while `numsright` is **empty**.

The **division score** of an index `i` is the **sum** of the number of `0`'s in `numsleft` and the number of `1`'s in `numsright`.

Return _**all distinct indices** that have the **highest** possible **division score**_. You may return the answer in **any order**.

**Example 1:**

**Input:** nums = [0,0,1,0]
**Output:** [2,4]
**Explanation:** Division at index
- 0: numsleft is []. numsright is [0,0,**1**,0]. The score is 0 + 1 = 1.
- 1: numsleft is [**0**]. numsright is [0,**1**,0]. The score is 1 + 1 = 2.
- 2: numsleft is [**0**,**0**]. numsright is [**1**,0]. The score is 2 + 1 = 3.
- 3: numsleft is [**0**,**0**,1]. numsright is [0]. The score is 2 + 0 = 2.
- 4: numsleft is [**0**,**0**,1,**0**]. numsright is []. The score is 3 + 0 = 3.
Indices 2 and 4 both have the highest possible division score 3.
Note the answer [4,2] would also be accepted.

**Example 2:**

**Input:** nums = [0,0,0]
**Output:** [3]
**Explanation:** Division at index
- 0: numsleft is []. numsright is [0,0,0]. The score is 0 + 0 = 0.
- 1: numsleft is [**0**]. numsright is [0,0]. The score is 1 + 0 = 1.
- 2: numsleft is [**0**,**0**]. numsright is [0]. The score is 2 + 0 = 2.
- 3: numsleft is [**0**,**0**,**0**]. numsright is []. The score is 3 + 0 = 3.
Only index 3 has the highest possible division score 3.

**Example 3:**

**Input:** nums = [1,1]
**Output:** [0]
**Explanation:** Division at index
- 0: numsleft is []. numsright is [**1**,**1**]. The score is 0 + 2 = 2.
- 1: numsleft is [1]. numsright is [**1**]. The score is 0 + 1 = 1.
- 2: numsleft is [1,1]. numsright is []. The score is 0 + 0 = 0.
Only index 0 has the highest possible division score 2.

**Constraints:**

* `n == nums.length`
* `1 <= n <= 105`
* `nums[i]` is either `0` or `1`.

# Approaches
## Brute Force Iteration
This approach directly simulates the process described in the problem. It iterates through every possible division index `i` from `0` to `n`. For each index, it calculates the score by explicitly counting the number of zeros in the left part (`nums_left`) and the number of ones in the right part (`nums_right`). It keeps track of the maximum score seen so far and the list of indices that achieve this score.
**Time:** O(n^2). For each of the `n+1` division points, we iterate over the array, which takes `O(n)` time. · **Space:** O(1) auxiliary space. The space for the result list is not counted as auxiliary space.
**Pros:** Simple to understand and implement.; Directly follows the problem definition.
**Cons:** Highly inefficient due to redundant calculations.; Time complexity is quadratic, which is too slow for large inputs (`n` up to 10^5).
### Explanation
We iterate through all possible division points `i` from `0` to `n`.
For each `i`, we perform two separate counts:
1.  Iterate from the beginning of the array up to `i-1` to count the zeros (`zerosLeft`).
2.  Iterate from index `i` to the end of the array to count the ones (`onesRight`).
The score for index `i` is `zerosLeft + onesRight`.
We maintain a variable `maxScore` and a list `resultIndices`.
If the current score is greater than `maxScore`, we update `maxScore` and replace `resultIndices` with a new list containing just `i`.
If the current score is equal to `maxScore`, we simply add `i` to `resultIndices`.
This process is repeated for all `n+1` possible division points.
The main drawback is the repeated counting. For each division point, we traverse significant portions of the array, leading to a quadratic time complexity.
```java
public List<Integer> maxScoreIndices(int[] nums) {
    int n = nums.length;
    List<Integer> result = new ArrayList<>();
    int maxScore = -1;

    for (int i = 0; i <= n; i++) {
        int zerosLeft = 0;
        for (int j = 0; j < i; j++) {
            if (nums[j] == 0) {
                zerosLeft++;
            }
        }

        int onesRight = 0;
        for (int j = i; j < n; j++) {
            if (nums[j] == 1) {
                onesRight++;
            }
        }

        int currentScore = zerosLeft + onesRight;

        if (currentScore > maxScore) {
            maxScore = currentScore;
            result.clear();
            result.add(i);
        } else if (currentScore == maxScore) {
            result.add(i);
        }
    }
    return result;
}
```
### Algorithm
- Initialize `maxScore` to -1 and `result` as an empty list.
- Loop through each possible division index `i` from `0` to `n`.
    - Calculate `zerosLeft` by iterating from index `0` to `i-1`.
    - Calculate `onesRight` by iterating from index `i` to `n-1`.
    - Compute `currentScore = zerosLeft + onesRight`.
    - If `currentScore > maxScore`, update `maxScore` to `currentScore` and reset `result` to contain only `i`.
    - If `currentScore == maxScore`, add `i` to `result`.
- Return `result`.

## Pre-computation using Prefix and Suffix Arrays
This approach optimizes the brute-force method by avoiding repeated calculations. It pre-computes the number of zeros to the left of every index and the number of ones to the right of every index. These values are stored in two separate arrays. Then, it iterates through all division points once more, calculating the score for each point in `O(1)` time using the pre-computed values.
**Time:** O(n). It takes three separate passes over the data: one for prefix zeros, one for suffix ones, and one to calculate scores. Each pass is `O(n)`. · **Space:** O(n). We use two additional arrays of size `n+1` to store the pre-computed counts.
**Pros:** Much more efficient than brute force with a linear time complexity.
**Cons:** Requires extra space proportional to the input size to store the prefix and suffix arrays.
### Explanation
The core idea is to pre-calculate the necessary counts to make the score calculation for each index `i` instantaneous.
We create a prefix sum array, `zerosPrefix`, of size `n+1`. `zerosPrefix[i]` will store the count of zeros in `nums[0...i-1]`. This can be computed in a single pass from left to right.
We create a suffix sum array, `onesSuffix`, of size `n+1`. `onesSuffix[i]` will store the count of ones in `nums[i...n-1]`. This can be computed in a single pass from right to left.
After populating these two arrays, we iterate from `i = 0` to `n`. The score for each division `i` is simply `zerosPrefix[i] + onesSuffix[i]`.
We then find the maximum score and all indices that achieve it, similar to the brute-force approach, but this time the score calculation is `O(1)`.
```java
public List<Integer> maxScoreIndices(int[] nums) {
    int n = nums.length;
    int[] zerosPrefix = new int[n + 1];
    int[] onesSuffix = new int[n + 1];

    // Calculate prefix sums of zeros
    for (int i = 0; i < n; i++) {
        zerosPrefix[i + 1] = zerosPrefix[i] + (nums[i] == 0 ? 1 : 0);
    }

    // Calculate suffix sums of ones
    for (int i = n - 1; i >= 0; i--) {
        onesSuffix[i] = onesSuffix[i + 1] + (nums[i] == 1 ? 1 : 0);
    }

    List<Integer> result = new ArrayList<>();
    int maxScore = -1;
    for (int i = 0; i <= n; i++) {
        int currentScore = zerosPrefix[i] + onesSuffix[i];
        if (currentScore > maxScore) {
            maxScore = currentScore;
            result.clear();
            result.add(i);
        } else if (currentScore == maxScore) {
            result.add(i);
        }
    }
    return result;
}
```
### Algorithm
- Create a `zerosPrefix` array of size `n+1`.
- Populate `zerosPrefix` such that `zerosPrefix[i]` is the count of zeros in `nums[0...i-1]`.
- Create an `onesSuffix` array of size `n+1`.
- Populate `onesSuffix` such that `onesSuffix[i]` is the count of ones in `nums[i...n-1]`.
- Initialize `maxScore` to -1 and `result` as an empty list.
- Loop through each division index `i` from `0` to `n`.
    - Calculate `currentScore = zerosPrefix[i] + onesSuffix[i]`.
    - Update `maxScore` and `result` based on `currentScore`.
- Return `result`.

## Optimized Single Pass Approach
This is the most efficient approach. It builds upon the observation that the score for a division at `i+1` can be calculated from the score at `i` in constant time. By making a single pass through the array, we can update the score as we move the division point, thus avoiding both redundant calculations and the need for extra storage arrays.
**Time:** O(n). We have an initial pass to count all ones (`O(n)`) and then a single pass through the array to update scores (`O(n)`). · **Space:** O(1) auxiliary space. We only use a few variables to keep track of scores, not requiring any extra arrays.
**Pros:** Optimal time complexity of `O(n)`.; Optimal space complexity of `O(1)` (auxiliary).; Requires only a single pass after an initial count, making it very efficient.
**Cons:** The logic for updating the score might be slightly less intuitive than the other approaches at first glance.
### Explanation
We can find the score for any division point `i` by updating the score from the previous division point `i-1`.
First, we calculate the initial score for the division at index `i=0`. In this case, `nums_left` is empty (0 zeros), and `nums_right` is the entire array. So, the initial score is just the total number of ones in `nums`.
We initialize `maxScore` with this initial score and our result list with index `0`.
Then, we iterate from `i = 0` to `n-1`, effectively moving the division point from `i` to `i+1`. When we do this, the element `nums[i]` moves from the right partition to the left partition.
- If `nums[i]` is `0`, the count of zeros on the left increases by one, and the count of ones on the right is unchanged. The score increases by 1.
- If `nums[i]` is `1`, the count of zeros on the left is unchanged, and the count of ones on the right decreases by one. The score decreases by 1.
We update the current score at each step and compare it with `maxScore` to maintain the list of indices with the highest score.
```java
public List<Integer> maxScoreIndices(int[] nums) {
    int n = nums.length;
    int ones = 0;
    for (int num : nums) {
        if (num == 1) {
            ones++;
        }
    }

    // Initial score for division at index 0
    // zerosLeft = 0, onesRight = total ones
    int currentScore = ones;
    int maxScore = currentScore;
    List<Integer> result = new ArrayList<>();
    result.add(0);

    // Iterate through the array to calculate scores for divisions 1 to n
    for (int i = 0; i < n; i++) {
        // When moving division from i to i+1, nums[i] moves to the left side.
        if (nums[i] == 0) {
            // Gained a 0 on the left, score increases
            currentScore++;
        } else { // nums[i] == 1
            // Lost a 1 on the right, score decreases
            currentScore--;
        }

        // currentScore is now the score for division at index i+1
        if (currentScore > maxScore) {
            maxScore = currentScore;
            result.clear();
            result.add(i + 1);
        } else if (currentScore == maxScore) {
            result.add(i + 1);
        }
    }
    return result;
}
```
### Algorithm
- Calculate the total number of ones in the array. This is the initial score for division at index `0`.
- Initialize `maxScore` with this initial score and `result` list containing `0`.
- Initialize `currentScore` to `maxScore`.
- Loop through the array from `i = 0` to `n-1`. In each iteration, we calculate the score for division at `i+1`.
    - If `nums[i]` is `0`, increment `currentScore`.
    - If `nums[i]` is `1`, decrement `currentScore`.
    - Compare the updated `currentScore` with `maxScore`.
    - If `currentScore > maxScore`, update `maxScore` and reset `result` to contain `i+1`.
    - If `currentScore == maxScore`, add `i+1` to `result`.
- Return `result`.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> maxScoreIndices(int[] nums) {
    int left = 0, right = sum(nums);
    int mx = right;
    List<Integer> ans = new ArrayList<>();
    ans.add(0);
    for (int i = 0; i < nums.length; ++i) {
      if (nums[i] == 0) {
        ++left;
      } else {
        --right;
      }
      int t = left + right;
      if (mx == t) {
        ans.add(i + 1);
      } else if (mx < t) {
        mx = t;
        ans.clear();
        ans.add(i + 1);
      }
    }
    return ans;
  }
private
  int sum(int[] nums) {
    int s = 0;
    for (int num : nums) {
      s += num;
    }
    return s;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> maxScoreIndices(vector<int> &nums) {
    int left = 0, right = accumulate(nums.begin(), nums.end(), 0);
    int mx = right;
    vector<int> ans;
    ans.push_back(0);
    for (int i = 0; i < nums.size(); ++i) {
      if (nums[i] == 0)
        ++left;
      else
        --right;
      int t = left + right;
      if (mx == t)
        ans.push_back(i + 1);
      else if (mx < t) {
        mx = t;
        ans.clear();
        ans.push_back(i + 1);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxScoreIndices(self, nums: List[int]) -> List[int]: left, right = 0, sum(nums) mx = right ans = [0] for i, num in enumerate(nums): if num == 0: left += 1 else: right -= 1 t = left + right if mx == t: ans . append(i + 1) elif mx < t: mx = t ans = [i + 1] return ans

```