Abstract / Summary

Given a list of numbers, find the largest number of groups you can split it into so that after sorting each group, the whole list becomes sorted.

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 55% (100k+ 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 implementation computes the maximum number of chunks into which an input array can be split so that sorting each chunk individually and concatenating the results yields a fully sorted array. The algorithm works by analyzing the permutation that maps each element from its original position to its position in the sorted order. It then counts the number of disjoint cycles in this permutation; each cycle corresponds to a chunk that can be isolated.

Key Steps

1. Prepare the sorted representation

The code first creates a list of pairs containing each element and its original index, then sorts this list by the element value.

size = len(arr)
nums = sorted([ (a, i) for i, a in enumerate(arr) ])

The sorted list nums preserves the original indices, which are needed to reconstruct the mapping from original positions to sorted positions.

2. Build the position-mapping array

A list moved of length size is allocated and filled such that moved[old] holds the new index of the element that originally resided at old.

moved = [0] * size
for new, (n, old) in enumerate(nums):
    moved[old] = new

This step translates the original ordering into a direct index-to-index mapping, enabling constant-time look-ups of where each element ends up after sorting.

3. Walk through the permutation and detect cycle boundaries

Two variables, last and result, drive the detection of cycle ends. last records the farthest index that belongs to the current cycle, while result accumulates the number of completed cycles (chunks).

last = 0
for i, (n, old) in enumerate(nums):
    new = moved[i]
    last = max(last, new, old)

    if i == last:
        result += 1

During each iteration the algorithm updates last with the maximum of the current last, the new position of the element originally at i, and the original index stored in the sorted tuple. When the loop index i catches up to last, the current cycle is closed, and a new chunk can be formed.

4. Return the final count

After processing all elements, the accumulated result is returned as the answer.

return result

Edge Cases Handled

When the input array is empty, size becomes zero, nums is an empty list, and the subsequent loops execute zero times, leaving result at its initial value of zero. This correctly reflects that no chunks can be formed from an empty collection.

A single-element array yields size == 1. The sorted list contains one tuple, the mapping array moved becomes [0], and the loop runs once. The last variable is updated to zero, the condition i == last holds, and result becomes one, indicating that the lone element forms a valid chunk.

If the array is already sorted, each element’s original index matches its sorted index. Consequently new and old are equal for every iteration, last never exceeds the current index, and the condition i == last triggers on every step. The algorithm therefore counts a chunk for each element, which is the maximal possible partition.

When the array is in reverse order, the mapping creates a single long cycle that spans the entire array. The last variable expands to the final index during the first few iterations, and only when i reaches that final index does the condition i == last become true. The result is one chunk, reflecting that the whole array must be sorted as a unit.

The code also gracefully handles arrays containing duplicate values. Python’s sort is stable, so equal elements retain their original relative order. The tuple (value, original_index) ensures that each duplicate is distinguished by its index, producing a well-defined permutation. The cycle detection logic therefore works correctly even when values repeat.

Performance Optimizations

The algorithm avoids repeated scanning of the array by constructing the moved array in a single pass after sorting. This pre-computed mapping enables constant-time retrieval of an element’s target position, eliminating the need for nested loops.

The use of max to maintain the farthest index of the current cycle (last) allows the detection of cycle boundaries without explicitly storing visited flags or constructing explicit cycle lists. This reduces auxiliary memory usage to a single integer and the moved array.

Sorting is performed on a list of tuples rather than on separate structures, which leverages Python’s highly optimized Timsort implementation. The tuple includes the original index, eliminating a later lookup step and keeping the overall number of passes over the data minimal.

By iterating over the sorted list nums rather than the original array, the code reuses the already-available ordering information, avoiding an extra pass to map values back to indices. This tight coupling of data preparation and cycle detection contributes to a streamlined execution flow.

Imagine you have a row of colorful blocks with numbers written on them, but they are all mixed up. The goal is to chop these blocks into the smallest possible groups so that if you sorted the blocks inside each group, the whole line of blocks would be in the perfect order from smallest to biggest.

This code acts like a scout looking through the line. First, it figures out where every block belongs by looking at all the numbers and sorting them in its head. It makes a map, which is basically a list that remembers the correct spot for every single block.

Then, the code starts walking down the line from the first block to the last. It keeps a special tally of the furthest spot any block in the current chunk needs to reach. As it moves along, it checks if the current position is the end of a chunk. It knows it reached the end of a group when the spot it is looking at matches the furthest spot any block in that group wants to go. Every time it finds the end of one of these sets, it adds one to the final count of chunks. It keeps doing this until every block is accounted for in a group.

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

not analyzed yet

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