All Divisions With the Highest Score of a Binary Array Solution
All Divisions With the Highest Score of a Binary Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
All Divisions With the Highest Score of a Binary Array is a medium coding problem on arrays and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a binary array nums of length n. Dividing it at index i (0 <= i <= n) splits it into left = nums[0..i - 1] and right = nums[i..n - 1] — either part may be empty (i = 0 or i = n).
The division score at i is the number of 0s in left plus the number of 1s in right.
Return all indices with the highest division score, in increasing order.
Example 1
Input: nums = [0,0,1,0]
Output: [2,4]
Explanation: Scores for i = 0..4 are 1, 2, 3, 2, 3. The highest, 3, occurs at i = 2 and i = 4.
Example 2
Input: nums = [0,0,0]
Output: [3]
Explanation: Putting every 0 on the left scores 3.
Example 3
Input: nums = [1,1]
Output: [0]
Explanation: Putting every 1 on the right scores 2.
Constraints
n == nums.length1 <= n <= 10^5nums[i] is either 0 or 1
Hints for All Divisions With the Highest Score of a Binary Array
Hint 1
Recounting both halves for each of the
n + 1divisions isO(n^2). How does the score change when the split moves one step right?Hint 2
Moving from
itoi + 1movesnums[i]from right to left: a0adds one point, a1loses one point.Hint 3
Start with the score at
i = 0(the count of 1s), update it step by step, and collect every index that matches the running maximum — resetting the list whenever a new maximum appears.
How to solve All Divisions With the Highest Score of a Binary Array
The score at consecutive split points differs by exactly +1 (a 0 crossed into the left) or -1 (a 1 left the right part). One sweep computes all n + 1 scores and keeps the indices of the maximum.
Approach
score= number of 1s innums(the division ati = 0);best = score,answer = [0].- For
i = 1 .. n:score += 1ifnums[i - 1] == 0, elsescore -= 1. - If
score > best, setbest = scoreandanswer = [i]; ifscore == best, appendi. - Return
answer.
Why it works
Moving the split from i - 1 to i transfers only nums[i - 1] between the parts, so the update is exact. The maintained list always holds every index seen so far whose score equals the best seen so far, in increasing order.
Complexity
- Time —
O(n) - Space —
O(1) besides the output
Pitfalls
- There are
n + 1divisions, including the empty-lefti = 0and the empty-righti = n. - Reset the list when a strictly higher score appears; append on a tie.
Reference solution
Python
from typing import List
def maxScoreIndices(nums: List[int]) -> List[int]:
score = sum(nums)
best = score
answer = [0]
for i in range(1, len(nums) + 1):
score += 1 if nums[i - 1] == 0 else -1
if score > best:
best = score
answer = [i]
elif score == best:
answer.append(i)
return answerJava
public static int[] maxScoreIndices(int[] nums) {
int score = 0;
for (int x : nums) score += x;
int best = score;
List<Integer> answer = new ArrayList<>();
answer.add(0);
for (int i = 1; i <= nums.length; i++) {
score += nums[i - 1] == 0 ? 1 : -1;
if (score > best) { best = score; answer.clear(); answer.add(i); }
else if (score == best) answer.add(i);
}
int[] res = new int[answer.size()];
for (int i = 0; i < res.length; i++) res[i] = answer.get(i);
return res;
}C++
vector<int> maxScoreIndices(vector<int>& nums) {
int score = 0;
for (int x : nums) score += x;
int best = score;
vector<int> answer{0};
for (int i = 1; i <= (int) nums.size(); i++) {
score += nums[i - 1] == 0 ? 1 : -1;
if (score > best) { best = score; answer.assign(1, i); }
else if (score == best) answer.push_back(i);
}
return answer;
}JavaScript
var maxScoreIndices = function(nums) {
var score = 0;
for (var k = 0; k < nums.length; k++) score += nums[k];
var best = score, answer = [0];
for (var i = 1; i <= nums.length; i++) {
score += nums[i - 1] === 0 ? 1 : -1;
if (score > best) { best = score; answer = [i]; }
else if (score === best) answer.push(i);
}
return answer;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Prefix Sum