Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2155.html
2155. All Divisions With the Highest Score of a Binary Array (Medium)
You are given a 0indexed binary array nums
of length n
. nums
can be divided at index i
(where 0 <= i <= n)
into two arrays (possibly empty) nums_{left}
and nums_{right}
:
nums_{left}
has all the elements ofnums
between index0
andi  1
(inclusive), whilenums_{right}
has all the elements of nums between indexi
andn  1
(inclusive). If
i == 0
,nums_{left}
is empty, whilenums_{right}
has all the elements ofnums
.  If
i == n
,nums_{left}
has all the elements of nums, whilenums_{right}
is empty.
The division score of an index i
is the sum of the number of 0
's in nums_{left}
and the number of 1
's in nums_{right}
.
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: nums_{left} is []. nums_{right} is [0,0,1,0]. The score is 0 + 1 = 1.  1: nums_{left} is [0]. nums_{right} is [0,1,0]. The score is 1 + 1 = 2.  2: nums_{left} is [0,0]. nums_{right} is [1,0]. The score is 2 + 1 = 3.  3: nums_{left} is [0,0,1]. nums_{right} is [0]. The score is 2 + 0 = 2.  4: nums_{left} is [0,0,1,0]. nums_{right} 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: nums_{left} is []. nums_{right} is [0,0,0]. The score is 0 + 0 = 0.  1: nums_{left} is [0]. nums_{right} is [0,0]. The score is 1 + 0 = 1.  2: nums_{left} is [0,0]. nums_{right} is [0]. The score is 2 + 0 = 2.  3: nums_{left} is [0,0,0]. nums_{right} 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: nums_{left} is []. nums_{right} is [1,1]. The score is 0 + 2 = 2.  1: nums_{left} is [1]. nums_{right} is [1]. The score is 0 + 1 = 1.  2: nums_{left} is [1,1]. nums_{right} is []. The score is 0 + 0 = 0. Only index 0 has the highest possible division score 2.
Constraints:
n == nums.length
1 <= n <= 10^{5}
nums[i]
is either0
or1
.
Similar Questions:
 Ones and Zeroes (Medium)
 Max Consecutive Ones II (Medium)
 Count Subarrays With More Ones Than Zeros (Medium)
 Array Partition I (Easy)
 Divide Array in Sets of K Consecutive Numbers (Medium)
Solution 1. Count Left Ones and Right Zeros on the fly
Let zero
/one
be the number of zeros/ones in the left/right part. Initially one = SUM(A)
.
For each i
, score = zero + one
. And we can update zero
and one
when we move A[i]
from right part to left part.

// OJ: https://leetcode.com/problems/alldivisionswiththehighestscoreofabinaryarray/ // Time: O(N) // Space: O(N) class Solution { public: vector<int> maxScoreIndices(vector<int>& A) { int N = A.size(), one = accumulate(begin(A), end(A), 0), zero = 0, mx = 0; vector<int> ans; for (int i = 0; i <= N; ++i) { int score = one + zero; if (score > mx) { ans = {i}; mx = score; } else if (score == mx) ans.push_back(i); if (i < N) { one = A[i] == 1; zero += A[i] == 0; } } return ans; } };

// Todo

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 ans ############ # 2155. All Divisions With the Highest Score of a Binary Array # https://leetcode.com/problems/alldivisionswiththehighestscoreofabinaryarray/ class Solution: def maxScoreIndices(self, nums: List[int]) > List[int]: n = len(nums) zeroes = [0] ones = [0] for x in nums: zeroes.append(zeroes[1] + int(x == 0)) ones.append(ones[1] + int(x == 1)) mp = collections.defaultdict(list) res = 0 for i in range(n + 1): left = zeroes[i]  zeroes[0] right = ones[1]  ones[i] count = left + right mp[count].append(i) res = max(res, count) return mp[res]
Note that here I marked extra space complexity as O(N)
because the ans
is used to store some temporary results whose length might be as long as N1
while the answer might be just of length 1. So, the extra space we used might be linear to the input but not strictly confined by the size of the real answer.
That said, we can make it O(1)
space by calculating the maximum score in one loop first then gather the ans
array in another loop. In this way, the size of the ans
is absolutely the same as the size of the real answer and won’t be linear to the input size. But, this requires two loops.
Solution 2. Prefix Sum
Let sum[i+1]
be A[0] + ... + A[i]
.
For index i
, there are i  sum[i]
zeros in the left part and sum[N]  sum[i]
ones in the right part.
So the score for i
is i  sum[i] + sum[N]  sum[i]
.

// OJ: https://leetcode.com/problems/alldivisionswiththehighestscoreofabinaryarray/ // Time: O(N) // Space: O(N) class Solution { public: vector<int> maxScoreIndices(vector<int>& A) { int N = A.size(), mx = 0; vector<int> sum(N + 1, 0), ans; for (int i = 0; i < N; ++i) sum[i + 1] = sum[i] + A[i]; for (int i = 0; i <= N; ++i) { int score = i  sum[i] + sum[N]  sum[i]; if (score > mx) { ans = {i}; mx = score; } else if (score == mx) ans.push_back(i); } return ans; } };

// Todo

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 ans ############ # 2155. All Divisions With the Highest Score of a Binary Array # https://leetcode.com/problems/alldivisionswiththehighestscoreofabinaryarray/ class Solution: def maxScoreIndices(self, nums: List[int]) > List[int]: n = len(nums) zeroes = [0] ones = [0] for x in nums: zeroes.append(zeroes[1] + int(x == 0)) ones.append(ones[1] + int(x == 1)) mp = collections.defaultdict(list) res = 0 for i in range(n + 1): left = zeroes[i]  zeroes[0] right = ones[1]  ones[i] count = left + right mp[count].append(i) res = max(res, count) return mp[res]
Discuss
https://leetcode.com/problems/alldivisionswiththehighestscoreofabinaryarray/discuss/1730117