{x}
blog image

All Divisions With the Highest Score of a Binary Array

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:

  • numsleft 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, numsleft is empty, while numsright has all the elements of nums.
  • If i == n, numsleft has all the elements of nums, while numsright is 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.length
  • 1 <= n <= 105
  • nums[i] is either 0 or 1.

Solution Explanation: Finding All Divisions with the Highest Score

This problem involves finding all indices in a binary array that, when used to divide the array into two subarrays, result in the highest possible division score. The division score is calculated as the sum of zeros in the left subarray and ones in the right subarray.

Approach:

Instead of iterating through all possible division points and recalculating scores for each, we can use a more efficient approach based on prefix sums and a single pass through the array.

  1. Initialization:

    • l0: Keeps track of the number of zeros in the left subarray. Initialized to 0.
    • r1: Keeps track of the number of ones in the right subarray. Initialized to the total number of ones in the entire nums array.
    • mx: Stores the maximum division score encountered so far. Initialized to r1 (score when the division is at index 0).
    • ans: A list (or vector) to store the indices with the maximum division score. Initialized with 0 (because the score at index 0 is r1).

  2. Iteration:

    • We iterate through the nums array. For each index i, we perform the following steps:
      • Update l0: If nums[i-1] is 0, increment l0. (The previous element is added to the left side)
      • Update r1: If nums[i-1] is 1, decrement r1. (The previous element is removed from the right side)
      • Calculate t: The current division score t is l0 + r1.
      • Update ans and mx:
        • If t == mx, it means we've found another index with the maximum score. Add i to ans.
        • If t > mx, it means we've found a new maximum score. Update mx to t, clear ans, and add i to ans.

  3. Return ans: After iterating through all indices, ans will contain all indices with the highest division score.

Time Complexity: O(n), where n is the length of the input array nums. We iterate through the array only once.

Space Complexity: O(1) in the best case (if only one index has the maximum score). In the worst case, it could be O(n), if all indices have the same maximum score and are added to ans. However, this is a relatively rare scenario. In most cases, the space usage remains constant.

Code Examples (Python):

class Solution:
    def maxScoreIndices(self, nums: List[int]) -> List[int]:
        l0, r1 = 0, sum(nums)
        mx = r1
        ans = [0]
        for i, x in enumerate(nums, 1):
            l0 += 1 - x  #Efficient way to add 1 if x is 0, otherwise 0
            r1 -= x
            t = l0 + r1
            if mx == t:
                ans.append(i)
            elif mx < t:
                mx = t
                ans = [i]
        return ans

The code in other languages (Java, C++, Go, TypeScript, Rust) follows the same logic, only differing in syntax and data structure usage. The core idea of using prefix sum like approach to efficiently calculate the scores remains the same across all implementations.