Watch 9 video solutions for All Divisions With the Highest Score of a Binary Array, a medium level problem involving Array. This walkthrough by Bro Coders has 980 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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).i == 0, numsleft is empty, while numsright has all the elements of nums.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.length1 <= n <= 105nums[i] is either 0 or 1.Problem Overview: You are given a binary array and can divide it at any index from 0 to n. The score of a division equals the number of 0s on the left plus the number of 1s on the right. The task is to compute this score for every possible division and return all indices that produce the maximum score.
Approach 1: Prefix and Suffix Sums (O(n) time, O(n) space)
This approach precomputes how many zeros appear to the left of every index and how many ones appear to the right. Build two arrays: a prefix array counting zeros while scanning left to right, and a suffix array counting ones while scanning right to left. For any division i, the score becomes prefixZero[i] + suffixOne[i]. Iterate through all divisions, compute the score, track the maximum, and collect all indices that match it. The idea relies on precomputation so each score lookup is constant time. Time complexity is O(n) for building the arrays and evaluating divisions, while space complexity is O(n) for the prefix and suffix arrays. This method clearly demonstrates the use of prefix sum techniques on an array.
Approach 2: Single Pass Calculation (O(n) time, O(1) space)
The score formula can be simplified so you do not need extra arrays. First count the total number of ones in the entire array. That value represents the right-side contribution when the division is at index 0. Then iterate through the array while maintaining two running values: zeros seen on the left and ones remaining on the right. When you move past an element, update the counters accordingly. For each position i, compute score = leftZeros + rightOnes, compare it with the best score seen so far, and update the result list if necessary. This transforms the problem into a simple linear scan over the array. Time complexity remains O(n), but space complexity drops to O(1) since only a few counters are maintained.
Recommended for interviews: The single-pass method is what most interviewers expect. It shows that you can derive the scoring formula and maintain running counts efficiently. The prefix/suffix approach is still valuable because it demonstrates the pattern of precomputing information for constant-time queries. Showing the prefix idea first and then optimizing to a single pass highlights strong problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix and Suffix Sums | O(n) | O(n) | When you want a clear and easy-to-reason solution using precomputed counts |
| Single Pass Calculation | O(n) | O(1) | Best choice for interviews or memory‑constrained scenarios |