All Divisions With the Highest Score of a Binary Array

All Divisions With the Highest Score of a Binary Array - Problem

Array Medium

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) nums_left and nums_right:

nums_left has all the elements of nums between index 0 and i - 1 (inclusive), while nums_right has all the elements of nums between index i and n - 1 (inclusive).

If i == 0, nums_left is empty, while nums_right has all the elements of nums.

If i == n, nums_left has all the elements of nums, while nums_right is empty.

The division score of an index i is the sum of the number of 0's in nums_left and the number of 1's in nums_right.

Return all distinct indices that have the highest possible division score. You may return the answer in any order.

Input & Output

Example 1 — Basic Case

$ Input: nums = [0,0,1,1,1]

› Output: [2]

💡 Note: Division at index 2: left=[0,0] has 2 zeros, right=[1,1,1] has 3 ones, score=2+3=5 (maximum)

Example 2 — Multiple Answers

$ Input: nums = [0,0,0]

› Output: [3]

💡 Note: Division at index 3: left=[0,0,0] has 3 zeros, right=[] has 0 ones, score=3+0=3 (maximum)

Example 3 — All Ones

$ Input: nums = [1,1]

› Output: [0]

💡 Note: Division at index 0: left=[] has 0 zeros, right=[1,1] has 2 ones, score=0+2=2 (maximum)

Constraints

1 ≤ nums.length ≤ 10⁵
nums[i] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input

Binary array [0,0,1,1,1] with possible division points

Scoring

Count 0s in left part + 1s in right part for each division

Output

Return all indices with maximum division score

Key Takeaway

🎯 Key Insight: We want zeros on the left and ones on the right to maximize the score

Asked in

G Google 45 a Amazon 35 M Microsoft 30 A Apple 25

The key insight is that we want to maximize zeros on the left and ones on the right. The optimal approach uses prefix sum technique to track running counts in O(n) time without recalculating. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	For each possible division point, count 0s in left part and 1s in right part
Prefix Sum Optimization	O(n)	O(1)	Pre-calculate total 1s, then iterate once tracking 0s on left and 1s on right

Brute Force — Algorithm Steps

Iterate through all possible division points i from 0 to n
For each i, count 0s in nums[0:i] and 1s in nums[i:n]
Track maximum score and all indices achieving it

Visualization

Tap to expand

Step-by-Step Walkthrough

Division at i=0

Left: [], Right: [0,0,1,1,1] → Score = 0 + 3 = 3

Division at i=1

Left: [0], Right: [0,1,1,1] → Score = 1 + 3 = 4

Find Maximum

Compare all scores and return indices with highest score

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* nums, int numsSize, int* returnSize) {
    int maxScore = -1;
    int* result = (int*)malloc((numsSize + 1) * sizeof(int));
    int resultSize = 0;
    
    for (int i = 0; i <= numsSize; i++) {
        // Count 0s in left part [0, i)
        int zerosLeft = 0;
        for (int j = 0; j < i; j++) {
            if (nums[j] == 0) zerosLeft++;
        }
        
        // Count 1s in right part [i, numsSize)
        int onesRight = 0;
        for (int j = i; j < numsSize; j++) {
            if (nums[j] == 1) onesRight++;
        }
        
        int score = zerosLeft + onesRight;
        
        if (score > maxScore) {
            maxScore = score;
            resultSize = 0;
            result[resultSize++] = i;
        } else if (score == maxScore) {
            result[resultSize++] = i;
        }
    }
    
    *returnSize = resultSize;
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(nums, numsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n+1 division points, we scan up to n elements to count 0s and 1s

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track counts and maximum score

✓ Linear Space

38.4K Views

Medium Frequency

~15 min Avg. Time

865 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler