Abstract / Summary

Find the smallest continuous part of an array that must be sorted so the whole array 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 39% (1+ million submissions).

Typical patterns to solve this problem:

• Array
• Greedy
• Monotonic Stack
• Sorting
• Stack
• Two Pointers

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 determines the length of the shortest continuous sub-array that, when sorted, makes the entire input array non-decreasing. It follows a straightforward strategy: create a sorted replica of the input, compare the two sequences element-by-element, and locate the first and last positions where they differ. The distance between those positions (inclusive) yields the required length. If no differences are found, the array is already sorted and the function returns zero.

Key Steps

Creating a sorted copy

n2 = sorted(nums.copy())

A shallow copy of the original list is produced to preserve the caller’s data. The built-in sorted routine generates a new list ordered in non-decreasing fashion. This step supplies a reference ordering against which the original array is examined.

Initialising the boundary markers

left = right = None

Two variables, left and right, are set to None to indicate that no mismatching indices have been discovered yet. Using a single sentinel value for both markers simplifies later checks.

Scanning for mismatches

for i in range(len(nums)):
    if nums[i] != n2[i]:
        left  = i if left == None else left
        right = i

The loop iterates over every index of the input. Whenever the element at the current position differs from the element at the same position in the sorted copy, the algorithm records the index. The first mismatch encountered assigns left; subsequent mismatches only update right. This ensures that left marks the earliest out-of-order element while right marks the latest.

Computing the result

return 0 if left == None else right - left + 1

If left remains None, the input was already sorted and the function returns zero. Otherwise, the length of the minimal sub-array is the inclusive distance between right and left.

Edge Cases Handled

When the input list is empty, the loop body never executes, leaving both markers as None. The final conditional therefore returns zero, correctly indicating that no sorting is required.

A single-element list follows the same path: the element trivially matches its sorted counterpart, so the function again yields zero.

Arrays that are already sorted but contain duplicate values also produce no mismatches, because each position matches the sorted copy exactly. The algorithm therefore returns zero for any already ordered sequence, regardless of repeated numbers.

If the entire array is in reverse order, every position will differ from the sorted copy. The first iteration sets left to zero, and each subsequent iteration updates right until it reaches the final index. The computed length then equals the full size of the array, which is the correct answer for a completely unsorted input.

Arrays with a mixture of sorted and unsorted segments, including cases where the unsorted region is at the beginning, middle, or end, are all captured because the scan records the earliest and latest mismatching indices, regardless of their location.

Performance Optimizations Observed

The implementation leverages Python’s built-in sorted function, which employs Timsort. Timsort adapts to existing order in the data, achieving faster sorting on partially sorted inputs without additional code.

By copying the list before sorting, the original data remains untouched, avoiding side effects that could force extra copying later in a larger program.

The conditional assignment for left (i if left == None else left) ensures that the left boundary is set only once, eliminating unnecessary writes during the scan.

The loop processes each element exactly once, and the final arithmetic operation to compute the length is constant-time. These choices keep the runtime overhead minimal given the overall algorithmic approach.

Imagine a long row of building blocks that should be in order from the smallest to the tallest. Sometimes, someone might accidentally swap a few blocks around so they get out of line. This code acts like a tiny detective to find which part of the row is messy. First, it makes a secret list that is perfectly organized from smallest to biggest. Then it looks at the messy row and compares it to the perfect one, one block at a time. It keeps a sharp eye out for any spot where a block does not match the perfectly organized version. It marks the first spot where things look wrong and also the very last spot where things look wrong. Once the detective has looked at every block, it identifies the slice between that first messy spot and the last messy spot, which is the section that needs to be fixed to make the whole row perfect again.

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			Rust		Go	TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai			Java
	everthis					JS
	fartem							Ruby
	FelixFan1122				C#
	fpdjsns	C++
	halfrost								Go
	haoel		Python
	JoshCrozier					JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	qiyuangong			Java
	ruoru						Rust
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	wisdompeak	C++
	YuriSpiridonov		Python
	zfang399	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
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fpdjsns	C++
halfrost	Go
haoel	Python
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
qiyuangong	Java
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
YuriSpiridonov	Python
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