All Divisions With the Highest Score of a Binary Array

Problem Description

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) nums_left and nums_right. The division score of an index i is the sum of the number of 0s in nums_left and the number of 1s in nums_right. Return all distinct indices that have the highest possible division score.

Key Insights

• The division score at an index depends on the number of 0s to the left of the index and the number of 1s to the right.
• We can compute the cumulative counts of 0s from the left and 1s from the right efficiently.
• This allows us to find the maximum division score and the corresponding indices in a single pass.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we will:

1. Create two arrays: leftCount to keep track of the cumulative number of 0s from the left and rightCount to keep track of the cumulative number of 1s from the right.
2. Iterate through the nums array to fill these arrays.
3. Compute the division score for each index using values from leftCount and rightCount.
4. Track the maximum score and collect all indices that match this score.

Code Solutions