#2155

All Divisions With the Highest Score of a Binary Array

specialist · 630 · lc medium +30 · verified · 65.5% accepted · 538 likes · top 70%

⚑ Prefix / Suffix Product

Description

You are given a 0-indexed binary array nums of length n. The array can be split at any index i (where 0 <= i <= n) into a left part and a right part (either may be empty):

 - The left part contains all elements at indices 0 through i - 1.

 - The right part contains all elements at indices i through n - 1.

 - When i == 0, the left part is empty and the right part is all of nums.

 - When i == n, the left part is all of nums and the right part is empty.

The division score at index i equals the number of 0s in the left part plus the number of 1s in the right part.

Return all indices that achieve the highest division score. The answer may be 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.

Code

1
2
3