Problem Description

You have a binary array nums (containing only 0s and 1s) that is 0-indexed with length n. You can divide this array at any index i (where 0 <= i <= n) into two parts:

• Left part (nums_left): Contains all elements from index 0 to i-1 (inclusive)
• Right part (nums_right): Contains all elements from index i to n-1 (inclusive)

Special cases:

• When i = 0: The left part is empty, and the right part contains the entire array
• When i = n: The left part contains the entire array, and the right part is empty

The division score at index i is calculated as:

• Count of 0s in the left part + Count of 1s in the right part

Your task is to find all indices that achieve the maximum possible division score and return them in any order.

For example, if nums = [0,0,1,0]:

• At index i = 0: left part is empty (0 zeros), right part is [0,0,1,0] (1 one), score = 0 + 1 = 1
• At index i = 1: left part is [0] (1 zero), right part is [0,1,0] (1 one), score = 1 + 1 = 2
• At index i = 2: left part is [0,0] (2 zeros), right part is [1,0] (1 one), score = 2 + 1 = 3
• At index i = 3: left part is [0,0,1] (2 zeros), right part is [0] (0 ones), score = 2 + 0 = 2
• At index i = 4: left part is [0,0,1,0] (3 zeros), right part is empty (0 ones), score = 3 + 0 = 3

The maximum score is 3, achieved at indices 2 and 4.

Intuition

To find the indices with the maximum division score, we need to efficiently calculate the score at each possible division point. The key insight is that we don't need to recalculate everything from scratch for each index.

Think about what happens as we move the division point from left to right:

• When we move from index i to i+1, we're essentially moving one element from the right part to the left part
• If that element is a 0, the left part gains one 0 (increasing the score by 1)
• If that element is a 1, the right part loses one 1 (decreasing the score by 1)

This observation leads us to use a sliding window or prefix sum approach. We can:

1. Start at index 0 where the left part is empty and the right part contains everything
2. Track two counters: l0 (zeros in left part) and r1 (ones in right part)
3. Initially, l0 = 0 and r1 = sum(nums) (total count of 1s in the array)
4. As we iterate through each element:
   • If we encounter a 0, increment l0 (adding to our score)
   • If we encounter a 1, decrement r1 (removing from our score)
   • Calculate the current score as l0 + r1

The clever use of x ^ 1 in the code is a bitwise trick: when x = 1, x ^ 1 = 0, and when x = 0, x ^ 1 = 1. So l0 += x ^ 1 increments l0 only when we see a 0.

By maintaining these running counts, we can calculate each division score in O(1) time, making the entire algorithm run in O(n) time with just a single pass through the array. We keep track of the maximum score seen so far and collect all indices that achieve this maximum.

Solution Approach

The solution uses a prefix sum technique to efficiently calculate division scores in a single pass through the array.

Algorithm Steps:

1. Initialize counters:

   • l0 = 0: Count of zeros in the left part (initially empty)
   • r1 = sum(nums): Count of ones in the right part (initially contains all elements)
   • mx = r1: Maximum score seen so far (initial score at index 0)
   • ans = [0]: List to store indices with maximum score

2. Iterate through the array:

   • For each element at position i-1 (using 1-based indexing in the loop):
     • Update l0: Add 1 if the current element is 0 (using l0 += x ^ 1)
     • Update r1: Subtract the current element value (if it's 1, we subtract 1; if it's 0, we subtract 0)
     • Calculate current score: t = l0 + r1

3. Track maximum scores:

   • If t == mx: Current score equals the maximum, add index i to answer list
   • If t > mx: Found a new maximum score
     • Update mx = t
     • Reset answer list to contain only current index: ans = [i]

Key Implementation Details:

• The loop uses enumerate(nums, 1) to start indexing from 1, which naturally handles the division points from 1 to n
• The XOR operation x ^ 1 flips the bit: returns 1 when x = 0, and 0 when x = 1
• r1 -= x efficiently updates the count of ones in the right part

Time Complexity: O(n) - Single pass through the array plus initial sum calculation
Space Complexity: O(1) - Only using a few variables (excluding the output array)

The elegance of this solution lies in maintaining running counts that can be updated in constant time as we slide the division point, avoiding the need to recalculate counts for each position.

Example Walkthrough

Let's trace through the algorithm with nums = [0,0,1,0]:

Initial Setup:

• l0 = 0 (zeros in left part, which is empty)
• r1 = sum([0,0,1,0]) = 1 (ones in right part, which has all elements)
• mx = 1 (initial maximum score)
• ans = [0] (index 0 has score = 0 + 1 = 1)

Iteration 1: Processing element at index 0 (value = 0):

• Move this 0 from right to left
• l0 += 0 ^ 1 = 0 + 1 = 1 (we moved a zero to the left)
• r1 -= 0 = 1 - 0 = 1 (no ones removed from right)
• Score at index 1: t = l0 + r1 = 1 + 1 = 2
• Since t (2) > mx (1): Update mx = 2, ans = [1]

Iteration 2: Processing element at index 1 (value = 0):

• Move this 0 from right to left
• l0 += 0 ^ 1 = 1 + 1 = 2 (another zero moved to left)
• r1 -= 0 = 1 - 0 = 1 (no ones removed from right)
• Score at index 2: t = l0 + r1 = 2 + 1 = 3
• Since t (3) > mx (2): Update mx = 3, ans = [2]

Iteration 3: Processing element at index 2 (value = 1):

• Move this 1 from right to left
• l0 += 1 ^ 1 = 2 + 0 = 2 (not a zero, so l0 unchanged)
• r1 -= 1 = 1 - 1 = 0 (removed the only one from right)
• Score at index 3: t = l0 + r1 = 2 + 0 = 2
• Since t (2) < mx (3): No changes to mx or ans

Iteration 4: Processing element at index 3 (value = 0):

• Move this 0 from right to left
• l0 += 0 ^ 1 = 2 + 1 = 3 (another zero moved to left)
• r1 -= 0 = 0 - 0 = 0 (no ones removed from right)
• Score at index 4: t = l0 + r1 = 3 + 0 = 3
• Since t (3) == mx (3): Add index 4 to answer, ans = [2, 4]

Final Result: [2, 4] - Both indices achieve the maximum score of 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums. The algorithm makes a single pass through the array in the for loop, performing constant-time operations for each element (XOR operation, addition, subtraction, and comparisons). The initial sum(nums) operation also takes O(n) time. Therefore, the overall time complexity is O(n) + O(n) = O(n).

Space Complexity: O(1) if we exclude the output array, or O(n) if we include it. The algorithm uses a fixed number of variables (l0, r1, mx, t, i, x) regardless of input size. However, the ans list can potentially store up to n+1 indices in the worst case (when all positions have the same maximum score). Following the reference answer's convention which states O(1), it appears the output array is not counted toward space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Consider the Empty Division Cases

Many developers forget that divisions at indices 0 and n are valid, where one part is empty. A common mistake is starting the loop from index 1 and ending at n-1, missing these edge cases.

Incorrect approach:

# Wrong: Missing index 0 and index n
for i in range(1, len(nums)):
    # Calculate score for division at i
    left_zeros = nums[:i].count(0)
    right_ones = nums[i:].count(1)

Solution: Include index 0 in the initial result and use enumerate(nums, 1) to naturally handle all division points from 0 to n.

2. Inefficient Score Calculation

A naive approach recalculates counts for each division point, leading to O(n²) time complexity.

Inefficient approach:

# Wrong: O(n²) time complexity
for i in range(len(nums) + 1):
    left_zeros = nums[:i].count(0)
    right_ones = nums[i:].count(1)
    score = left_zeros + right_ones

Solution: Use prefix sum technique with running counters that update in O(1) time as you traverse the array once.

3. Incorrect Counter Updates

Misunderstanding how to update the counters when moving an element from right to left partition.

Common mistakes:

# Wrong: Always incrementing/decrementing by 1
left_zeros += 1  # Wrong if current element is 1
right_ones -= 1  # Wrong if current element is 0

# Wrong: Confusing the logic
left_zeros += value  # Should be (1 - value) or (value ^ 1)

Solution:

• For left_zeros: Add 1 only if the element is 0, use value ^ 1
• For right_ones: Subtract the actual value (1 if it's a 1, 0 if it's a 0)

4. Overwriting Results Instead of Collecting All Maximum Indices

Returning only the last index with maximum score instead of all indices.

Wrong approach:

max_score = 0
result = 0  # Single value instead of list
for i in range(len(nums) + 1):
    if score >= max_score:  # Using >= instead of proper comparison
        max_score = score
        result = i  # Overwrites previous indices

Solution: Maintain a list of indices and properly handle the two cases:

• When score equals maximum: append to the list
• When score exceeds maximum: reset the list with the new index