Abstract / Summary

Split the array into the largest number of groups where each group's max is less than the next group's min.

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 64% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy
• Monotonic Stack
• Sorting
• Stack

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 defines a Solution class with a single method maxChunksToSorted. The method receives a list of integers arr that represents a permutation of the numbers 0 through len(arr)-1. Its purpose is to compute the maximum number of chunks into which the array can be split so that sorting each chunk individually and concatenating the results yields a fully sorted array. The algorithm proceeds in a single linear pass, maintaining a running maximum (high) and a counter (result). Whenever the current index matches the running maximum, a chunk boundary is identified and the counter is incremented.

Key Steps

The core logic is expressed in three distinct operations inside the loop.

for pos, n in enumerate(arr):
    if high < n:
        high = n
    if pos == high:
        result += 1
        high = -1

• The loop iterates over each element together with its position.
• The first conditional updates high to the greatest value seen so far. This ensures that high always reflects the furthest index that must be included in the current chunk to accommodate all elements encountered.
• The second conditional checks whether the current position pos has reached the value stored in high. When this condition holds, all elements up to this point can be safely isolated as a chunk because no later element is smaller than any element inside the chunk. At that moment result is incremented and high is reset to -1 to start tracking the next chunk.

The method concludes by returning the accumulated result.

return result

Edge Cases Handled

The algorithm gracefully handles several boundary conditions without additional code.

When the input list is empty, the for loop body never executes, leaving result at its initial value of 0. The method therefore returns 0, which correctly represents that no chunks can be formed.

If the array consists of a single element, the loop runs once. The first conditional sets high to that element (which must be 0 in a valid permutation). Since pos is also 0, the second conditional triggers, increments result to 1, and resets high. The final return yields 1, indicating that the whole array forms a single valid chunk.

For a fully sorted array such as [0, 1, 2, 3], each iteration updates high to the current element, and the equality pos == high holds at every step. Consequently, result is incremented for each element, producing a chunk count equal to the array length. This matches the expectation that each element can be its own chunk.

Conversely, for a reverse-sorted permutation like [3, 2, 1, 0], high quickly becomes the maximum value 3 on the first iteration and remains unchanged until the loop reaches position 3. Only at that point does pos == high become true, resulting in a single chunk that encompasses the entire array. This demonstrates that the algorithm correctly postpones chunk formation until all larger values have been observed.

The reset of high to -1 after a chunk is closed ensures that the next chunk starts with a clean state, even if the subsequent element is 0. Since -1 is less than any possible array value, the first conditional will always update high on the next iteration, preserving correctness across consecutive chunks.

Performance Optimizations

The implementation achieves its goal with a single traversal of the input list, avoiding any auxiliary data structures. By maintaining only two integer variables (result and high), the memory footprint remains constant regardless of input size. The use of enumerate provides both index and value without extra lookups, and the conditional checks are simple integer comparisons, which are inexpensive operations in Python.

Resetting high to -1 after each chunk eliminates the need for a separate flag to indicate the start of a new chunk. This choice leverages the fact that all array elements are non-negative, allowing the sentinel value -1 to serve as an implicit “uninitialized” marker. Consequently, the algorithm avoids additional branching or state variables, contributing to a tight inner loop that runs efficiently even for large inputs.

Imagine a long line of numbered train cars that are all mixed up. The goal is to cut the train into the biggest number of little packs possible so that when each pack is sorted, the whole train is in perfect order from smallest to biggest.

The code starts by looking at the first train car. It keeps track of the biggest number it has seen so far inside the current piece of the train. It keeps moving along, checking each car one by one. If the car it is looking at has a number that is bigger than the others, it remembers that as the new high score. It also knows exactly which spot in the line each car belongs in based on its number.

When the position in the line matches the highest number found in that group, it means all the cars that belong in that section are finally present. Because the group is complete and contains exactly the right numbers, a cut is made to create a finished chunk. After making the cut, the count goes up by one, and it starts looking for the next group all over again.

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	JS	Rust			C	Go	TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	fengvyi	C++
	JoshCrozier				JS
	lkwq007			Python
	lzl124631x	C++
	ruoru					Rust
	Shamik07						Dart
	suxrobGM							C#
	trung-hn			Python
	varunu28		Java
	vthwang		Java
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
JoshCrozier	JavaScript
lkwq007	Python
lzl124631x	C++
ruoru	Rust
Shamik07	Dart
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
zfang399	C++

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