Abstract / Summary

Split the array so that both parts have equal sums and find the earliest split point.

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 76% (100k+ submissions).

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 minimumIndex method receives a list of integers and returns the smallest index at which the list can be split into two non-empty parts such that a value that is dominant (appears more than half the time in the whole list) remains dominant in both resulting partitions. If no such split exists the method returns -1.

Key Steps

Determine the dominant element

The algorithm first builds a frequency map for all values. While populating the map it checks whether any count has already crossed the majority threshold (size / 2). The first value that satisfies this condition is recorded as the dominant element.

size = len(nums)
dominant = None
freq = defaultdict(int)
for n in nums:
    freq[n] += 1
    if freq[n] * 2 > size:
        dominant = n

Initialise partition counters

Two counters are prepared: left tracks how many dominant elements have been moved to the left partition, and right holds the remaining count of the dominant element that is still in the right partition. right is initialised with the total frequency of the dominant value.

left  = 0
right = freq[dominant]

Scan to locate the split position

The method iterates over the list while maintaining the current split position (pos = i + 1). Whenever the current element equals the dominant value, the counters are updated to reflect the transfer of that element from the right side to the left side. After each transfer the algorithm checks whether the dominant element now exceeds half of the elements in both partitions. If the condition holds, the index just before the split (pos - 1) is returned immediately.

for i, n in enumerate(nums):
    pos = i + 1
    if n == dominant:
        left  += 1
        right -= 1
        if left * 2 > pos and right * 2 > (size - pos):
            return pos - 1

If the loop finishes without finding a valid split, the method returns -1.

return -1

Edge Cases Handled

When the input list contains no element that appears more than half the time, the variable dominant remains None. In that situation the subsequent logic never satisfies the split condition, and the method correctly falls through to return -1.

If the dominant element occupies the entire list, the initial right counter equals size. The first iteration moves one occurrence to the left side, and the condition left * 2 > pos becomes true only after enough dominant elements have been transferred to make the left partition a strict majority of its own size. The algorithm therefore handles cases where the split must occur deep into the array.

When the list length is one, the loop never produces a split because a split would create an empty partition; the method returns -1, which aligns with the requirement for non-empty parts.

The code also gracefully handles an empty list: size becomes 0, the frequency loop does nothing, dominant stays None, and the final return yields -1.

Performance Optimizations

The solution performs a single pass to compute frequencies and identify the dominant element, avoiding a second full scan for that purpose. The subsequent scan that searches for the split updates counters in constant time per element, allowing an early exit as soon as a valid split is detected. By storing only the total count of the dominant element and two integer counters, the algorithm uses a minimal amount of additional memory regardless of input size. The arithmetic checks (left * 2 > pos and right * 2 > (size - pos)) are simple integer operations, ensuring fast evaluation without the overhead of division or floating-point calculations.

Imagine a long train made of many colorful blocks. Some colors appear much more often than others. The code first looks through the whole train to find the color that shows up most frequently, which is called the dominant color.

Once that color is found, the code starts walking along the train from the very front to the back. It thinks about cutting the train into two smaller pieces at every spot it passes. As it moves, it keeps track of how many blocks of the dominant color are in the left piece and how many are in the right piece.

When the code cuts the train, it checks two things at once. It looks at the left piece to see if the dominant color makes up more than half of that section. At the same time, it looks at the right piece to see if the dominant color also makes up more than half of that section. If both sides have enough of that special color, the code has found the perfect spot for the cut. If it reaches the end of the train and cannot find a spot where both sides have enough of the color, it lets everyone know that no such split exists.

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			Java		C++		Python	TS
	WalkCCC			Java		C++		Python
	leetcode.ca			Java		C++	Go	Python	TS
	Progiez			Java		C++		Python
github	charles-wangkai			Java
	everthis	JS
	fsq		Rust
	JoshCrozier	JS
	Shamik07				Dart
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	Rust
JoshCrozier	JavaScript
Shamik07	Dart

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