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.
This approach utilizes prefix and suffix array concepts. We create a prefix sum array for counting zeros up to each index and a suffix sum array for counting ones in reverse. This allows us to calculate the score for any division point using the information from these two arrays.
The provided Python code computes the maximum score indices using prefix sums to count zeros from the start and suffix sums to count ones from the end. For each potential division point, the score is calculated as the sum of zeros before the division and ones after the division.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), for storing prefix and suffix arrays.
This approach attempts to compute the maximum score by maintaining a running count of zeros and ones in a single pass, rather than using additional arrays for prefix and suffix storage.
This C implementation calculates the total number of ones initially, then proceeds linearly maintaining running counts of zeros and ones to determine scores at each division point.
C
JavaScript
C#
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), auxiliary space not considering the result array.
We start from i = 0, using two variables l0 and r1 to respectively record the number of 1s to the left and right of i. Initially, l0 = 0, while r1 = sum nums.
We iterate through the array nums. For each i, we update l0 and r1, calculate the current grouping score t = l0 + r1. If t equals the current maximum grouping score mx, then we add i to the answer array. If t is greater than mx, we update mx to t, clear the answer array, and then add i to the answer array.
After the iteration ends, we return the answer array.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Prefix and Suffix Sums | Time Complexity: O(n), where n is the length of the array. |
| Single Pass Calculation | Time Complexity: O(n), where n is the length of the array. |
| Prefix Sum | — |
| 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 |
2155 All Divisions With the Highest Score of a Binary Array || Weekly Contest 278 || LeetCode 2155 • Bro Coders • 980 views views
Watch 8 more video solutions →Practice All Divisions With the Highest Score of a Binary Array with our built-in code editor and test cases.
Practice on FleetCode