Problem

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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:

1
2
3
4
5
6
7
8

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:

1
2
3
4
5
6
7

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 <= 10^5
  • nums[i] is either 0 or 1.

Solution

Method 1 – Prefix Sums

Intuition

The key idea is to efficiently compute, for every possible division index, the number of zeros to the left and the number of ones to the right. By precomputing prefix sums of zeros and total ones, we can calculate the division score for each index in constant time.

Approach

  1. Count Total Ones:
  • Compute the total number of ones in the array (total_ones).
  1. Iterate and Track Prefix Zeros:
  • Initialize prefix_zeros to 0.
  • For each index i from 0 to n (inclusive):
    • The number of zeros in numsleft is prefix_zeros.
    • The number of ones in numsright is total_ones - ones_seen_so_far.
    • The division score is their sum.
    • Track the maximum score and all indices achieving it.
    • If i < n and nums[i] == 0, increment prefix_zeros.
    • If i < n and nums[i] == 1, increment ones_seen_so_far.
  1. Return Indices:
  • Return all indices with the maximum score.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
   vector<int> maxScoreIndices(vector<int>& nums) {
      int total_ones = 0, n = nums.size();
      for (int x : nums) total_ones += x;
      vector<int> ans;
      int max_score = -1, prefix_zeros = 0, ones_seen = 0;
      for (int i = 0; i <= n; ++i) {
        int score = prefix_zeros + (total_ones - ones_seen);
        if (score > max_score) {
           max_score = score;
           ans.clear();
           ans.push_back(i);
        } else if (score == max_score) {
           ans.push_back(i);
        }
        if (i < n) {
           if (nums[i] == 0) prefix_zeros++;
           else ones_seen++;
        }
      }
      return ans;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
   public List<Integer> maxScoreIndices(int[] nums) {
      int totalOnes = 0, n = nums.length;
      for (int x : nums) totalOnes += x;
      List<Integer> ans = new ArrayList<>();
      int maxScore = -1, prefixZeros = 0, onesSeen = 0;
      for (int i = 0; i <= n; ++i) {
        int score = prefixZeros + (totalOnes - onesSeen);
        if (score > maxScore) {
           maxScore = score;
           ans.clear();
           ans.add(i);
        } else if (score == maxScore) {
           ans.add(i);
        }
        if (i < n) {
           if (nums[i] == 0) prefixZeros++;
           else onesSeen++;
        }
      }
      return ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
   def maxScoreIndices(self, nums: list[int]) -> list[int]:
      total_ones = sum(nums)
      n = len(nums)
      ans: list[int] = []
      max_score = -1
      prefix_zeros = 0
      ones_seen = 0
      for i in range(n + 1):
        score = prefix_zeros + (total_ones - ones_seen)
        if score > max_score:
           max_score = score
           ans = [i]
        elif score == max_score:
           ans.append(i)
        if i < n:
           if nums[i] == 0:
              prefix_zeros += 1
           else:
              ones_seen += 1
      return ans

Complexity

  • ⏰ Time complexity: O(N) — Single pass through the array.
  • 🧺 Space complexity: O(1) (excluding output list).