Abstract / Summary

Split the array into two parts so that all numbers in the first part are less than or equal to all numbers in the second part.

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 50% (200k+ 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 implementation defines a method that receives an integer array and returns the smallest index that can split the array into two non-empty parts such that every element on the left side is not greater than any element on the right side. The algorithm relies on two min-heaps: one representing the values that are still to be processed and another accumulating the values that have already been seen.

Key Steps

Preparing the heaps

next = nums.copy()
heapify(next)          # creates a min-heap of the remaining values
bad = []               # will become a min-heap of the values already visited

A shallow copy of the input list is made so that the original order is preserved. The copy is transformed into a min-heap, which allows constant-time access to the smallest element that has not yet been examined. An empty list bad is prepared to serve as the second heap.

Scanning the array

for i, n in enumerate(nums, 1):
    heappush(bad, n)
    # remove small values
    while bad and next[0] == bad[0]:
        heappop(next)
        heappop(bad)

    # no element on the left side is smaller than any value on the right side
    if not bad:
        return i

The loop iterates over the input array while maintaining a 1-based index i. Each element n is inserted into the bad heap, which now contains all values seen so far.

The inner while loop removes the smallest elements from both heaps as long as they match. Because both heaps are min-heaps, bad[0] and next[0] give the current minima. When the minima are equal, the element is present on both sides of the prospective partition and can be discarded from consideration. This removal continues until the smallest remaining element on the left side is larger than the smallest element that still resides on the right side.

When the bad heap becomes empty, it means that every element that has been processed is no longer smaller than any element that remains. At that moment the current index i satisfies the partition condition, and the method returns it.

Edge Cases Handled

When the input consists of a single element, the copy heap next initially contains that element. After pushing the element into bad, the inner loop removes the matching pair, leaving bad empty, and the method returns 1, which is the only valid split point.

If all elements are identical, each insertion into bad immediately matches the smallest element in next. The inner loop repeatedly removes matching pairs, and the first iteration empties bad, causing the method to return 1.

For a strictly decreasing sequence, each newly seen element is smaller than any element that remains on the right. Consequently, the inner loop never removes elements, and bad never becomes empty until the final iteration, at which point the method returns the length of the array.

Conversely, for a strictly increasing sequence, the first element is already the smallest overall. The inner loop removes the matching pair right away, leaving bad empty, and the method returns 1.

Duplicate values are naturally accommodated because the equality check in the inner loop removes only one occurrence from each heap per iteration, preserving correct accounting for multiple identical numbers.

Performance Optimizations

The algorithm leverages heap data structures to keep track of minima with logarithmic update cost. Inserting a new element into bad and removing the smallest element from either heap both run in O(log n) time, which is efficient for the incremental nature of the problem.

By discarding matching minima as soon as they appear, the method avoids unnecessary comparisons later in the scan. This early elimination reduces the size of both heaps, which in turn speeds up subsequent heap operations.

The early-exit condition (if not bad: return i) allows the function to stop processing as soon as a valid partition is found, preventing a full traversal of the array in many typical cases.

Finally, using a copy of the input list for the next heap ensures that the original array remains unchanged, eliminating the need for additional bookkeeping or restoration steps.

Imagine a long train made of many colorful toy blocks. Each block has a number on it. The goal is to cut the train into two pieces. The rule for making the cut is that every single block in the front piece must have a number that is smaller than or the same as every single block in the back piece.

To find the spot to cut, the computer starts looking at the blocks one by one from the left. It keeps a pile of all the blocks it has seen so far. It also keeps a special list of all the blocks that are still waiting to be looked at in the order they were already standing.

For every block it passes, the computer adds that block to its pile of seen items. It checks if the smallest block in its seen pile happens to be the same as the smallest block waiting in the train. If they match, it knows those blocks are not causing any trouble, so it removes them both from their piles.

The computer keeps doing this until its pile of seen blocks is empty. When the pile is empty, it means that every block left behind in the front part is perfectly ready and smaller than everything waiting in the back part. That is the moment to slice the train.

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

Time: loglinear
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++	Python		Java			TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java		Go
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fsq	C++
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM					C#
	trung-hn		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
trung-hn	Python

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