All Divisions With the Highest Score of a Binary Array

Medium
1858.

All Divisions With the Highest Score of a Binary Array

All Divisions With the Highest Score of a Binary Array is a medium coding problem on arrays and prefix sum, asked in Amazon and Google interviews.

You are given a binary array nums of length n. Dividing it at index i (0 <= i <= n) splits it into left = nums[0..i - 1] and right = nums[i..n - 1] — either part may be empty (i = 0 or i = n).

The division score at i is the number of 0s in left plus the number of 1s in right.

Return all indices with the highest division score, in increasing order.

Example 1

Input
nums = [0,0,1,0]
Output
[2,4]
Explanation
Scores for i = 0..4 are 1, 2, 3, 2, 3. The highest, 3, occurs at i = 2 and i = 4.

Example 2

Input
nums = [0,0,0]
Output
[3]
Explanation
Putting every 0 on the left scores 3.

Example 3

Input
nums = [1,1]
Output
[0]
Explanation
Putting every 1 on the right scores 2.

Constraints

  • n == nums.length
  • 1 <= n <= 10^5
  • nums[i] is either 0 or 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var maxScoreIndices = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

All Divisions With the Highest Score of a Binary Array Solution

All Divisions With the Highest Score of a Binary Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

All Divisions With the Highest Score of a Binary Array is a medium coding problem on arrays and prefix sum, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Prefix Sum
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a binary array nums of length n. Dividing it at index i (0 <= i <= n) splits it into left = nums[0..i - 1] and right = nums[i..n - 1] — either part may be empty (i = 0 or i = n).

The division score at i is the number of 0s in left plus the number of 1s in right.

Return all indices with the highest division score, in increasing order.

Example 1

Input: nums = [0,0,1,0]
Output: [2,4]
Explanation: Scores for i = 0..4 are 1, 2, 3, 2, 3. The highest, 3, occurs at i = 2 and i = 4.

Example 2

Input: nums = [0,0,0]
Output: [3]
Explanation: Putting every 0 on the left scores 3.

Example 3

Input: nums = [1,1]
Output: [0]
Explanation: Putting every 1 on the right scores 2.

Constraints

  • n == nums.length
  • 1 <= n <= 10^5
  • nums[i] is either 0 or 1

Hints for All Divisions With the Highest Score of a Binary Array

  1. Hint 1

    Recounting both halves for each of the n + 1 divisions is O(n^2). How does the score change when the split moves one step right?

  2. Hint 2

    Moving from i to i + 1 moves nums[i] from right to left: a 0 adds one point, a 1 loses one point.

  3. Hint 3

    Start with the score at i = 0 (the count of 1s), update it step by step, and collect every index that matches the running maximum — resetting the list whenever a new maximum appears.

How to solve All Divisions With the Highest Score of a Binary Array

The score at consecutive split points differs by exactly +1 (a 0 crossed into the left) or -1 (a 1 left the right part). One sweep computes all n + 1 scores and keeps the indices of the maximum.

Approach

  1. score = number of 1s in nums (the division at i = 0); best = score, answer = [0].
  2. For i = 1 .. n: score += 1 if nums[i - 1] == 0, else score -= 1.
  3. If score > best, set best = score and answer = [i]; if score == best, append i.
  4. Return answer.

Why it works

Moving the split from i - 1 to i transfers only nums[i - 1] between the parts, so the update is exact. The maintained list always holds every index seen so far whose score equals the best seen so far, in increasing order.

Complexity

  • Time — O(n)
  • Space — O(1) besides the output

Pitfalls

  • There are n + 1 divisions, including the empty-left i = 0 and the empty-right i = n.
  • Reset the list when a strictly higher score appears; append on a tie.

Reference solution

Python

from typing import List

def maxScoreIndices(nums: List[int]) -> List[int]:
    score = sum(nums)
    best = score
    answer = [0]
    for i in range(1, len(nums) + 1):
        score += 1 if nums[i - 1] == 0 else -1
        if score > best:
            best = score
            answer = [i]
        elif score == best:
            answer.append(i)
    return answer

Java

public static int[] maxScoreIndices(int[] nums) {
    int score = 0;
    for (int x : nums) score += x;
    int best = score;
    List<Integer> answer = new ArrayList<>();
    answer.add(0);
    for (int i = 1; i <= nums.length; i++) {
        score += nums[i - 1] == 0 ? 1 : -1;
        if (score > best) { best = score; answer.clear(); answer.add(i); }
        else if (score == best) answer.add(i);
    }
    int[] res = new int[answer.size()];
    for (int i = 0; i < res.length; i++) res[i] = answer.get(i);
    return res;
}

C++

vector<int> maxScoreIndices(vector<int>& nums) {
    int score = 0;
    for (int x : nums) score += x;
    int best = score;
    vector<int> answer{0};
    for (int i = 1; i <= (int) nums.size(); i++) {
        score += nums[i - 1] == 0 ? 1 : -1;
        if (score > best) { best = score; answer.assign(1, i); }
        else if (score == best) answer.push_back(i);
    }
    return answer;
}

JavaScript

var maxScoreIndices = function(nums) {
    var score = 0;
    for (var k = 0; k < nums.length; k++) score += nums[k];
    var best = score, answer = [0];
    for (var i = 1; i <= nums.length; i++) {
        score += nums[i - 1] === 0 ? 1 : -1;
        if (score > best) { best = score; answer = [i]; }
        else if (score === best) answer.push(i);
    }
    return answer;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Prefix Sum