We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

All Divisions With the Highest Score of a Binary Array

Number: 2261

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a binary array nums, we want to find all indices i (from 0 to n, inclusive) where dividing the array into nums_left = nums[0...i-1] and nums_right = nums[i...n-1] results in the highest possible division score. The division score is defined as the number of 0's in nums_left plus the number of 1's in nums_right.

Key Insights

  • Use a single pass to calculate total ones in the array (which gives the initial count for the right side when i = 0).
  • As you iterate from i = 0 to n, maintain a running count of zeros in the left part.
  • For each index, compute the score as current count of left zeros plus current count of right ones.
  • When moving the split, update the counts accordingly: if the current element is 0, it contributes to left zeros; if it is 1, it is removed from the right side.
  • Track the maximum score seen and record indices matching that score.

Space and Time Complexity

Time Complexity: O(n) – we make one pass through the array. Space Complexity: O(1) – only a few counters and variables are used (excluding the output list).

Solution

The solution uses a greedy one-pass approach. First, count the total number of ones in the input array, which represents the count of ones in the right partition when the split is at index 0. Then iterate through the array considering each possible division index. For each index, compute the score by adding the accumulated left zeros and the current right ones count. If the current element is 0, increment the left zero count; if it is 1, decrement the right ones count (since it moves from the right to the left after the split). Track the maximum score observed and store the indices that achieve this maximum.

Code Solutions

# Python solution with detailed comments
def maxScoreIndices(nums):
    # Count the total number of ones in nums (initial right ones count)
    totalOnes = sum(nums)
    
    # Initialize counters for left zeros and current right ones
    leftZeros = 0
    rightOnes = totalOnes

    maxScore = -1        # To keep track of the highest score observed
    bestIndices = []     # List to store indices with the highest score

    n = len(nums)
    
    # Iterate over every possible division index from 0 to n
    for i in range(n + 1):
        # Calculate the current division score
        currentScore = leftZeros + rightOnes
        
        # Update if we found a new maximum score
        if currentScore > maxScore:
            maxScore = currentScore
            bestIndices = [i]
        # If current score equals maximum, append this index
        elif currentScore == maxScore:
            bestIndices.append(i)
        
        # Only update counters if we haven't processed all elements
        if i < n:
            # If the current element is 0, it will contribute to left side after the split
            if nums[i] == 0:
                leftZeros += 1
            # If the current element is 1, it moves out from the right partition
            else:
                rightOnes -= 1
    
    return bestIndices

# Example usage:
print(maxScoreIndices([0,0,1,0]))  # Output: [2, 4]
← Back to All Questions