Skip to main content
Talentd

All Divisions With the Highest Score of a Binary Array - Solution & Explanation

MediumArray15 min readAsked at: Google
Practice this problem

Problem Statement

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.

Approach Overview

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 1: Prefix and Suffix Sums

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.

Code

PythonJavaC++

Python

Java

C++

Complexity

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), for storing prefix and suffix arrays.

Try this approach in the editor →

Approach 2: Single Pass Calculation

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.

Code

CJavaScriptC#

C

JavaScript

C#

Complexity

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), auxiliary space not considering the result array.

Try this approach in the editor →

Approach 3: Prefix Sum

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).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix and Suffix Sums

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), for storing prefix and suffix arrays.

Single Pass Calculation

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), auxiliary space not considering the result array.

Prefix Sum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix and Suffix SumsO(n)O(n)When you want a clear and easy-to-reason solution using precomputed counts
Single Pass CalculationO(n)O(1)Best choice for interviews or memory‑constrained scenarios

Video Solution

2155 All Divisions With the Highest Score of a Binary Array || Weekly Contest 278 || LeetCode 2155 • Bro Coders • 986 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is All Divisions With the Highest Score of a Binary Array easy or hard?
The problem is rated Medium because the scoring formula is not immediately obvious. Once you recognize that the score depends on zeros to the left and ones to the right, it reduces to a straightforward linear scan with O(n) time complexity.
All Divisions With the Highest Score of a Binary Array Python/Java solution
Most implementations follow the same logic across languages. Count total ones, iterate through the array updating left zero count and right one count, compute the score at each index, and record indices with the maximum score. This approach works in Python, Java, C++, JavaScript, C#, and C with O(n) time.
How to solve All Divisions With the Highest Score of a Binary Array in O(n)?
First count the total number of ones in the array. Then iterate from left to right, keeping track of zeros seen so far and ones remaining to the right. For each division index compute score = leftZeros + rightOnes, update the maximum score, and store indices that match it. This linear scan processes each element once.
What is the best approach for All Divisions With the Highest Score of a Binary Array?
The most efficient approach is a single-pass scan that tracks zeros on the left and remaining ones on the right. Start by counting total ones in the array, then iterate once while updating counters and computing the score for each division. This achieves O(n) time and O(1) space complexity.
Is All Divisions With the Highest Score of a Binary Array asked at Google/Amazon/Meta?
Problems involving prefix counts, array scanning, and score maximization frequently appear in interviews at companies like Amazon, Google, and Meta. Variations of this problem test your ability to derive formulas and maintain running statistics efficiently in O(n) time.
What data structure is used in All Divisions With the Highest Score of a Binary Array?
The core data structure is a simple array traversal with integer counters. Some implementations also use prefix and suffix arrays to store cumulative counts of zeros and ones, which allows constant-time score calculation for every division.
What is the time complexity of All Divisions With the Highest Score of a Binary Array?
The optimal solution runs in O(n) time because the array is scanned once while maintaining running counts of zeros and ones. Each division score is computed in constant time. Space complexity can be O(1) with the single-pass method or O(n) if prefix and suffix arrays are used.

Ready to solve this problem?

Practice All Divisions With the Highest Score of a Binary Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Array Partition

Next

Count Subarrays With More Ones Than Zeros