life is too short for a diary

Tags: leetcode hashmap array java python

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) nums_{left} and nums_{right}:

nums_{left} 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, nums_{left} is empty, while nums_{right} has all the elements of nums.
If i == n, nums_{left} has all the elements of nums, while nums_{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 orde

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

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

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

We can maintain two window `left`

with size 0 and `right`

with full length of array. For each iteration, we will increase the length of `left`

window and reduce the `right`

window. We will also keep track of number of zeros in the `left`

window and number of ones in `right`

window. The `maximum sum`

of `left + right`

will contain the highest score.

The maxium key in **hashmap** will contain the list of indices with the highest score.

comments powered by Disqus