Abstract / Summary

Find all ways to split a binary array into two non-empty parts where the part with more 1s is as large as possible.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 66% (50k+ submissions).

Typical patterns to solve this problem:

• Array

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes all split positions in a binary array that yield the maximum possible score. A split position is defined as the index where the array is divided into a left part and a right part; the score for a split is the number of zeros in the left part plus the number of ones in the right part. The algorithm returns a list of all indices that achieve the highest score.

Key Steps

The method begins by initializing the result list with a single element 0, which represents the split before any elements.

result = [0]

The length of the input array is stored, and two counters are prepared: zero for the number of zeros encountered so far, and ones for the total number of ones in the entire array. The initial high score is set to the total number of ones because a split at position 0 yields a score equal to the count of ones on the right side.

size = len(nums)
zero = 0
ones = sum(nums)
high = ones

Degenerate situations are handled early. If the array contains no ones, the optimal split is after the last element, so the method returns [size]. If the array consists entirely of ones, the optimal split is before the first element, so it returns [0].

if ones == 0:
    return [size]
if ones == size:
    return [0]

The core loop iterates over each element together with its index. For each iteration the split point is defined as i + 1, representing the position immediately after the current element.

for i, n in enumerate(nums):
    split = i + 1

Inside the loop the counters are updated: a zero increments zero; a one decrements ones because that one moves from the right side to the left side as the split advances.

if n == 0:
    zero += 1
else:
    ones -= 1

The current score is computed as the sum of zeros on the left and ones on the right.

score = zero + ones

If this score exceeds the previously recorded high score, the high score is updated and the result list is reset to contain only the current split. If the score matches the high score, the current split is appended to the result list.

if high < score:
    high = score
    result = [split]
elif high == score:
    result.append(split)

After processing all elements, the method returns the list of split indices that achieve the maximum score.

return result

Edge Cases Handled

The algorithm explicitly checks for the situation where the input contains only zeros. In that case every possible split yields a score of zero, and the rightmost split (after the last element) is returned as the sole optimal index.

When the input consists solely of ones, any split yields a score equal to the number of ones on the right side, which is maximized by placing the split before the first element. The method returns [0] for this scenario.

The early return for these two extremes prevents unnecessary iteration and ensures correct handling of arrays where the general scoring logic would otherwise produce identical scores for all positions.

Performance Optimizations

The implementation achieves linear time execution by traversing the array exactly once. The total number of ones is computed once with sum(nums), and thereafter the count of ones on the right side is maintained incrementally by decrementing ones whenever a one is encountered. This avoids recomputing the right-side count at each iteration.

Similarly, the count of zeros on the left side is built up incrementally, eliminating the need for a separate prefix sum array. The use of simple integer variables for zero, ones, and high keeps the per-iteration work minimal.

Early exits for the all-zero and all-one cases prevent the loop from running when the answer is already known, saving work for those degenerate inputs.

Overall, the method relies on constant-time arithmetic operations inside a single pass, which constitutes an efficient solution for the problem.

Imagine a long line of toy boxes, where some hold a zero and others hold a one. There is a game to find the best place to draw a line through the row to make the total score as high as possible.

The score is calculated by counting all the zeros to the left of the line and adding them to all the ones to the right of the line. Before starting, the game looks at everything in the row to see how many ones there are in total.

The game then starts walking through the line from start to finish. At every single spot between the boxes, it draws an imaginary line. Whenever it sees a zero, it keeps track of it, and whenever it passes a one, it takes that one away from the pile on the right.

By adding those collected zeros and the remaining ones, it finds a score for that spot. If a spot gets a higher score than any spot seen before, everything found earlier is forgotten and only this new spot is kept. If a spot gets the same high score as another spot, it is added to the collection of best spots. Once every spot has been checked, the collection of best spots is ready.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java	Python				TS
	WalkCCC	C++		Java	Python
	leetcode.ca	C++		Java	Python		Go	Rust	TS
	Progiez	C++		Java	Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007				Python
	suxrobGM					C#
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality