LeetCode 2155 - All Divisions With the Highest Score of a Binary Array

LeetCode Problem 2155

Difficulty: 🟡 Medium
Topics: Array

Solution

Problem Understanding

The problem gives us a binary array nums, meaning every element is either 0 or 1. We are allowed to divide the array at any index i where 0 <= i <= n, and that division creates two parts:

• The left part contains elements from index 0 to i - 1
• The right part contains elements from index i to n - 1

The division point itself is between elements, not on an element. Because i can be 0 or n, one side is allowed to be empty.

For each division index i, we calculate a score defined as:

• Number of 0s in the left part
• Plus number of 1s in the right part

The goal is to find every division index that achieves the maximum possible score.

The input size can be as large as 10^5, which immediately tells us that quadratic solutions will likely be too slow. A solution that repeatedly scans the array for every division point would perform poorly. We need something closer to linear time.

Several edge cases are important:

• Dividing at index 0, where the left side is empty
• Dividing at index n, where the right side is empty
• Arrays containing only 0s
• Arrays containing only 1s
• Multiple division points producing the same maximum score

The problem guarantees the array contains only binary values, which simplifies counting logic considerably.

Approaches

Brute Force Approach

A straightforward approach is to try every possible division index from 0 to n.

For each division:

• Count how many 0s exist in the left side
• Count how many 1s exist in the right side
• Compute the score
• Track the maximum score and corresponding indices

This approach is correct because it explicitly evaluates every valid division. However, for each division index, we may scan large portions of the array again.

If the array length is n, then:

• There are n + 1 division points
• Each division may require up to O(n) work

This leads to O(n^2) time complexity, which is too slow for n = 10^5.

Optimal Prefix Counting Approach

The key observation is that adjacent division points differ only by one element moving from the right side to the left side.

Suppose we move division index from i to i + 1:

• If nums[i] == 0, then the left side gains one additional zero
• If nums[i] == 1, then the right side loses one one

Instead of recomputing counts from scratch, we can maintain running counts while scanning once through the array.

We begin by counting how many 1s exist in the entire array. This represents the score at division index 0, because:

• Left side has zero 0s
• Right side contains all original 1s

Then we sweep through the array:

• When encountering a 0, increase left-zero count
• When encountering a 1, decrease right-one count

At every step, compute the current score efficiently in constant time.

This transforms the problem into a linear scan.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Recomputes counts for every division
Optimal	O(n)	O(1) excluding output	Maintains running counts while scanning once

Algorithm Walkthrough

1. Count the total number of 1s in the array.

This value represents the number of ones initially present in the right partition when the division index is 0. 2. Initialize two variables:

• left_zeros = 0
• right_ones = total number of ones

At division index 0, the score is:

left_zeros + right_ones 3. Initialize:

• max_score
• result

Start with division index 0 as the current best candidate. 4. Iterate through the array from left to right.

At position i, the element nums[i] moves from the right partition into the left partition. 5. Update counts depending on the current element.

• If the value is 0, increment left_zeros
• If the value is 1, decrement right_ones

6. Compute the score for division index i + 1.

The division after processing element i corresponds to placing the cut immediately after that element. 7. Compare the score against the current maximum.

• If the score is larger, reset the answer list
• If the score equals the maximum, append the division index

8. Continue until all division points are processed.
9. Return the list of best division indices.

Why it works

The algorithm maintains an invariant:

• left_zeros always equals the number of zeros in the left partition
• right_ones always equals the number of ones in the right partition

Because each step correctly updates these counts as one element crosses the division boundary, every computed score is accurate. Since all division indices are evaluated exactly once, the algorithm is guaranteed to find all indices with the maximum score.

Python Solution

from typing import List

class Solution:
    def maxScoreIndices(self, nums: List[int]) -> List[int]:
        right_ones = sum(nums)
        left_zeros = 0

        max_score = right_ones
        result = [0]

        for i, value in enumerate(nums):
            if value == 0:
                left_zeros += 1
            else:
                right_ones -= 1

            current_score = left_zeros + right_ones
            division_index = i + 1

            if current_score > max_score:
                max_score = current_score
                result = [division_index]
            elif current_score == max_score:
                result.append(division_index)

        return result

The implementation begins by counting all 1s in the array using sum(nums). Since the array is binary, summing the array directly gives the total number of ones.

The variables left_zeros and right_ones represent the two parts of the score formula. Initially, the left partition is empty, so left_zeros starts at 0. The right partition initially contains the entire array, so right_ones starts as the total number of ones.

The algorithm initializes the best score using division index 0. This avoids special-case logic later.

The loop processes each element exactly once. After updating counts, the algorithm computes the score corresponding to the division immediately after the current element, which is why the division index is i + 1.

Whenever a larger score is found, the result list is reset. When an equal score is found, the division index is appended.

The algorithm performs only constant work per element, giving linear runtime.

Go Solution

func maxScoreIndices(nums []int) []int {
	rightOnes := 0

	for _, value := range nums {
		rightOnes += value
	}

	leftZeros := 0
	maxScore := rightOnes
	result := []int{0}

	for i, value := range nums {
		if value == 0 {
			leftZeros++
		} else {
			rightOnes--
		}

		currentScore := leftZeros + rightOnes
		divisionIndex := i + 1

		if currentScore > maxScore {
			maxScore = currentScore
			result = []int{divisionIndex}
		} else if currentScore == maxScore {
			result = append(result, divisionIndex)
		}
	}

	return result
}

The Go implementation follows the same logic as the Python version.

Slices in Go naturally handle dynamic result storage through append. Since the problem constraints are small enough for standard integer operations, there are no integer overflow concerns.

Unlike Python, Go does not provide a direct built-in sum function for slices, so the total number of ones is computed manually with a loop.

The returned slice is never nil because division index 0 is always valid and included initially.

Worked Examples

Example 1

Input:

nums = [0,0,1,0]

Initial state:

• right_ones = 1
• left_zeros = 0
• Initial score at division 0 = 1

Step	Current Value	left_zeros	right_ones	Division Index	Score	Result
Initial	-	0	1	0	1	[0]
i=0	0	1	1	1	2	[1]
i=1	0	2	1	2	3	[2]
i=2	1	2	0	3	2	[2]
i=3	0	3	0	4	3	[2,4]

Final answer:

[2,4]

Example 2

Input:

nums = [0,0,0]

Initial state:

• right_ones = 0
• left_zeros = 0

Step	Current Value	left_zeros	right_ones	Division Index	Score	Result
Initial	-	0	0	0	0	[0]
i=0	0	1	0	1	1	[1]
i=1	0	2	0	2	2	[2]
i=2	0	3	0	3	3	[3]

Final answer:

[3]

Example 3

Input:

nums = [1,1]

Initial state:

• right_ones = 2
• left_zeros = 0

Step	Current Value	left_zeros	right_ones	Division Index	Score	Result
Initial	-	0	2	0	2	[0]
i=0	1	0	1	1	1	[0]
i=1	1	0	0	2	0	[0]

Final answer:

[0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The array is scanned once to count ones and once more to evaluate divisions
Space	O(1) excluding output	Only a few integer variables are maintained

The algorithm uses two linear passes over the array. The first computes the total number of ones, and the second evaluates every division point. Since each element is processed a constant number of times, the runtime is linear.

The auxiliary memory usage remains constant because only counters and bookkeeping variables are used. The returned result list is not counted toward auxiliary space complexity.

Test Cases

from typing import List

class Solution:
    def maxScoreIndices(self, nums: List[int]) -> List[int]:
        right_ones = sum(nums)
        left_zeros = 0

        max_score = right_ones
        result = [0]

        for i, value in enumerate(nums):
            if value == 0:
                left_zeros += 1
            else:
                right_ones -= 1

            current_score = left_zeros + right_ones
            division_index = i + 1

            if current_score > max_score:
                max_score = current_score
                result = [division_index]
            elif current_score == max_score:
                result.append(division_index)

        return result

solution = Solution()

assert solution.maxScoreIndices([0, 0, 1, 0]) == [2, 4]  # provided example with two answers
assert solution.maxScoreIndices([0, 0, 0]) == [3]  # all zeros
assert solution.maxScoreIndices([1, 1]) == [0]  # all ones
assert solution.maxScoreIndices([0]) == [1]  # single zero
assert solution.maxScoreIndices([1]) == [0]  # single one
assert solution.maxScoreIndices([0, 1]) == [1]  # balanced small array
assert solution.maxScoreIndices([1, 0]) == [0, 2]  # multiple optimal divisions
assert solution.maxScoreIndices([0, 1, 0, 1, 0]) == [1, 3, 5]  # repeated ties
assert solution.maxScoreIndices([1, 0, 1, 0, 1]) == [0, 2]  # alternating pattern
assert solution.maxScoreIndices([0, 0, 0, 0, 0]) == [5]  # larger all-zero case
assert solution.maxScoreIndices([1, 1, 1, 1, 1]) == [0]  # larger all-one case

Test	Why
[0,0,1,0]	Validates multiple optimal answers
[0,0,0]	Tests all-zero input
[1,1]	Tests all-one input
[0]	Smallest array containing zero
[1]	Smallest array containing one
[0,1]	Simple mixed case
[1,0]	Confirms ties at different boundaries
[0,1,0,1,0]	Tests repeated equal maximum scores
[1,0,1,0,1]	Tests alternating pattern
[0,0,0,0,0]	Larger all-zero scenario
[1,1,1,1,1]	Larger all-one scenario

Edge Cases

One important edge case occurs when the array contains only zeros. In this situation, every division moving right increases the number of zeros on the left, while the number of ones on the right always remains zero. The optimal answer is therefore division index n. A buggy implementation might forget to evaluate the final division point after the last element. This implementation naturally handles it because every iteration evaluates division index i + 1.

Another important edge case is an array containing only ones. Here, the initial division at index 0 already has the maximum possible score because the right partition contains every one in the array. As the division moves right, the score strictly decreases. Some implementations accidentally overwrite the initial best score before evaluating later positions. This solution explicitly initializes the answer using division index 0, ensuring correctness.

A third important edge case involves multiple optimal division points. For example, [1,0] produces the same maximum score at division indices 0 and 2. An incorrect solution might keep only one best index instead of all valid indices. This implementation properly appends indices whenever the current score equals the maximum score.

Another subtle edge case is the smallest valid input size, where n = 1. With only one element, there are still two valid division points: before the element and after the element. The algorithm correctly evaluates both because it initializes division 0 before entering the loop and evaluates division 1 during the first iteration.