All Divisions With the Highest Score of a Binary Array
MedPrompt
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:
numslefthas all the elements ofnumsbetween index0andi - 1(inclusive), whilenumsrighthas all the elements of nums between indexiandn - 1(inclusive).- If
i == 0,numsleftis empty, whilenumsrighthas all the elements ofnums. - If
i == n,numslefthas all the elements of nums, whilenumsrightis 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 either0or1.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. It iterates through every possible division index i from 0 to n. For each index, it calculates the score by explicitly counting the number of zeros in the left part (nums_left) and the number of ones in the right part (nums_right). It keeps track of the maximum score seen so far and the list of indices that achieve this score.
Algorithm
- Initialize
maxScoreto -1 andresultas an empty list. - Loop through each possible division index
ifrom0ton.- Calculate
zerosLeftby iterating from index0toi-1. - Calculate
onesRightby iterating from indexiton-1. - Compute
currentScore = zerosLeft + onesRight. - If
currentScore > maxScore, updatemaxScoretocurrentScoreand resetresultto contain onlyi. - If
currentScore == maxScore, additoresult.
- Calculate
- Return
result.
Walkthrough
We iterate through all possible division points i from 0 to n.
For each i, we perform two separate counts:
- Iterate from the beginning of the array up to
i-1to count the zeros (zerosLeft). - Iterate from index
ito the end of the array to count the ones (onesRight). The score for indexiiszerosLeft + onesRight. We maintain a variablemaxScoreand a listresultIndices. If the current score is greater thanmaxScore, we updatemaxScoreand replaceresultIndiceswith a new list containing justi. If the current score is equal tomaxScore, we simply additoresultIndices. This process is repeated for alln+1possible division points. The main drawback is the repeated counting. For each division point, we traverse significant portions of the array, leading to a quadratic time complexity.
public List<Integer> maxScoreIndices(int[] nums) { int n = nums.length; List<Integer> result = new ArrayList<>(); int maxScore = -1; for (int i = 0; i <= n; i++) { int zerosLeft = 0; for (int j = 0; j < i; j++) { if (nums[j] == 0) { zerosLeft++; } } int onesRight = 0; for (int j = i; j < n; j++) { if (nums[j] == 1) { onesRight++; } } int currentScore = zerosLeft + onesRight; if (currentScore > maxScore) { maxScore = currentScore; result.clear(); result.add(i); } else if (currentScore == maxScore) { result.add(i); } } return result;}Complexity
Time
O(n^2). For each of the `n+1` division points, we iterate over the array, which takes `O(n)` time.
Space
O(1) auxiliary space. The space for the result list is not counted as auxiliary space.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem definition.
Cons
Highly inefficient due to redundant calculations.
Time complexity is quadratic, which is too slow for large inputs (
nup to 10^5).
This approach optimizes the brute-force method by avoiding repeated calculations. It pre-computes the number of zeros to the left of every index and the number of ones to the right of every index. These values are stored in two separate arrays. Then, it iterates through all division points once more, calculating the score for each point in O(1) time using the pre-computed values.
Algorithm
- Create a
zerosPrefixarray of sizen+1. - Populate
zerosPrefixsuch thatzerosPrefix[i]is the count of zeros innums[0...i-1]. - Create an
onesSuffixarray of sizen+1. - Populate
onesSuffixsuch thatonesSuffix[i]is the count of ones innums[i...n-1]. - Initialize
maxScoreto -1 andresultas an empty list. - Loop through each division index
ifrom0ton.- Calculate
currentScore = zerosPrefix[i] + onesSuffix[i]. - Update
maxScoreandresultbased oncurrentScore.
- Calculate
- Return
result.
Walkthrough
The core idea is to pre-calculate the necessary counts to make the score calculation for each index i instantaneous.
We create a prefix sum array, zerosPrefix, of size n+1. zerosPrefix[i] will store the count of zeros in nums[0...i-1]. This can be computed in a single pass from left to right.
We create a suffix sum array, onesSuffix, of size n+1. onesSuffix[i] will store the count of ones in nums[i...n-1]. This can be computed in a single pass from right to left.
After populating these two arrays, we iterate from i = 0 to n. The score for each division i is simply zerosPrefix[i] + onesSuffix[i].
We then find the maximum score and all indices that achieve it, similar to the brute-force approach, but this time the score calculation is O(1).
public List<Integer> maxScoreIndices(int[] nums) { int n = nums.length; int[] zerosPrefix = new int[n + 1]; int[] onesSuffix = new int[n + 1]; // Calculate prefix sums of zeros for (int i = 0; i < n; i++) { zerosPrefix[i + 1] = zerosPrefix[i] + (nums[i] == 0 ? 1 : 0); } // Calculate suffix sums of ones for (int i = n - 1; i >= 0; i--) { onesSuffix[i] = onesSuffix[i + 1] + (nums[i] == 1 ? 1 : 0); } List<Integer> result = new ArrayList<>(); int maxScore = -1; for (int i = 0; i <= n; i++) { int currentScore = zerosPrefix[i] + onesSuffix[i]; if (currentScore > maxScore) { maxScore = currentScore; result.clear(); result.add(i); } else if (currentScore == maxScore) { result.add(i); } } return result;}Complexity
Time
O(n). It takes three separate passes over the data: one for prefix zeros, one for suffix ones, and one to calculate scores. Each pass is `O(n)`.
Space
O(n). We use two additional arrays of size `n+1` to store the pre-computed counts.
Trade-offs
Pros
Much more efficient than brute force with a linear time complexity.
Cons
Requires extra space proportional to the input size to store the prefix and suffix arrays.
This is the most efficient approach. It builds upon the observation that the score for a division at i+1 can be calculated from the score at i in constant time. By making a single pass through the array, we can update the score as we move the division point, thus avoiding both redundant calculations and the need for extra storage arrays.
Algorithm
- Calculate the total number of ones in the array. This is the initial score for division at index
0. - Initialize
maxScorewith this initial score andresultlist containing0. - Initialize
currentScoretomaxScore. - Loop through the array from
i = 0ton-1. In each iteration, we calculate the score for division ati+1.- If
nums[i]is0, incrementcurrentScore. - If
nums[i]is1, decrementcurrentScore. - Compare the updated
currentScorewithmaxScore. - If
currentScore > maxScore, updatemaxScoreand resetresultto containi+1. - If
currentScore == maxScore, addi+1toresult.
- If
- Return
result.
Walkthrough
We can find the score for any division point i by updating the score from the previous division point i-1.
First, we calculate the initial score for the division at index i=0. In this case, nums_left is empty (0 zeros), and nums_right is the entire array. So, the initial score is just the total number of ones in nums.
We initialize maxScore with this initial score and our result list with index 0.
Then, we iterate from i = 0 to n-1, effectively moving the division point from i to i+1. When we do this, the element nums[i] moves from the right partition to the left partition.
- If
nums[i]is0, the count of zeros on the left increases by one, and the count of ones on the right is unchanged. The score increases by 1. - If
nums[i]is1, the count of zeros on the left is unchanged, and the count of ones on the right decreases by one. The score decreases by 1. We update the current score at each step and compare it withmaxScoreto maintain the list of indices with the highest score.
public List<Integer> maxScoreIndices(int[] nums) { int n = nums.length; int ones = 0; for (int num : nums) { if (num == 1) { ones++; } } // Initial score for division at index 0 // zerosLeft = 0, onesRight = total ones int currentScore = ones; int maxScore = currentScore; List<Integer> result = new ArrayList<>(); result.add(0); // Iterate through the array to calculate scores for divisions 1 to n for (int i = 0; i < n; i++) { // When moving division from i to i+1, nums[i] moves to the left side. if (nums[i] == 0) { // Gained a 0 on the left, score increases currentScore++; } else { // nums[i] == 1 // Lost a 1 on the right, score decreases currentScore--; } // currentScore is now the score for division at index i+1 if (currentScore > maxScore) { maxScore = currentScore; result.clear(); result.add(i + 1); } else if (currentScore == maxScore) { result.add(i + 1); } } return result;}Complexity
Time
O(n). We have an initial pass to count all ones (`O(n)`) and then a single pass through the array to update scores (`O(n)`).
Space
O(1) auxiliary space. We only use a few variables to keep track of scores, not requiring any extra arrays.
Trade-offs
Pros
Optimal time complexity of
O(n).Optimal space complexity of
O(1)(auxiliary).Requires only a single pass after an initial count, making it very efficient.
Cons
The logic for updating the score might be slightly less intuitive than the other approaches at first glance.
Solutions
Solution
class Solution {public List<Integer> maxScoreIndices(int[] nums) { int left = 0, right = sum(nums); int mx = right; List<Integer> ans = new ArrayList<>(); ans.add(0); for (int i = 0; i < nums.length; ++i) { if (nums[i] == 0) { ++left; } else { --right; } int t = left + right; if (mx == t) { ans.add(i + 1); } else if (mx < t) { mx = t; ans.clear(); ans.add(i + 1); } } return ans; }private int sum(int[] nums) { int s = 0; for (int num : nums) { s += num; } return s; }}class Solution {public: vector<int> maxScoreIndices(vector<int> &nums) { int left = 0, right = accumulate(nums.begin(), nums.end(), 0); int mx = right; vector<int> ans; ans.push_back(0); for (int i = 0; i < nums.size(); ++i) { if (nums[i] == 0) ++left; else --right; int t = left + right; if (mx == t) ans.push_back(i + 1); else if (mx < t) { mx = t; ans.clear(); ans.push_back(i + 1); } } return ans; }};class Solution: def maxScoreIndices(self, nums: List[int]) -> List[int]: left, right = 0, sum(nums) mx = right ans = [0] for i, num in enumerate(nums): if num == 0: left += 1 else: right -= 1 t = left + right if mx == t: ans . append(i + 1) elif mx < t: mx = t ans = [i + 1] return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.