Abstract / Summary

Given an array, determine if you can change at most one element to make the array non-decreasing.

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 26% (1+ million 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 provided implementation determines whether a list of integers can become non-decreasing by modifying at most one element. It augments the original list with sentinel values at both ends, then performs two linear scans. The first scan attempts to correct a single disorder by adjusting either the current element or its predecessor. The second scan verifies that the resulting sequence is fully ordered. Early termination occurs as soon as more than one disorder is detected, guaranteeing a quick answer for most inputs.

Key Steps

The algorithm begins by creating a new list that sandwiches the input between two extreme sentinel values. This is expressed by the statement:

nums = [ -999999 ] + nums + [ +999999 ]

The sentinel -999999 is smaller than any realistic input value, while +999999 is larger. Their presence eliminates the need for explicit boundary checks when accessing nums[i-2] or nums[i+1] during the scans.

A counter named misplaced tracks how many violations of the non-decreasing property have been encountered. The first linear pass starts at index 2 and examines each triple of consecutive elements:

for i in range(2, len(nums)):
    if nums[i] < nums[i - 1]:
        if nums[i] >= nums[i - 2]:
            nums[i - 1] = nums[i]
        else:
            nums[i] = nums[i - 1]
        misplaced += 1
        if misplaced == 2:
            return False

When a disorder is found (nums[i] < nums[i-1]), the inner condition decides which element to modify. If the current element is still not smaller than the element two positions back, it can replace its predecessor, effectively lowering the larger value. Otherwise the current element is raised to match its predecessor. In either case the violation count is incremented, and the loop aborts immediately if a second violation appears.

After the corrective pass, a second verification loop runs over the same range:

for i in range(2, len(nums)):
    if nums[i] < nums[i - 1]:
        return False

If any remaining disorder is detected, the function returns False. If the loop completes without finding a problem, the function returns True, indicating that at most one modification suffices.

Edge Cases Handled

The sentinel values ensure that the algorithm gracefully handles inputs of length zero or one, because the loops start at index 2 and the sentinel pair guarantees that the comparison logic never accesses an out-of-range index. For a single-element list, the first pass never triggers a violation, and the second pass also completes without issue, resulting in True.

When the input is already sorted, the condition nums[i] < nums[i-1] never holds, so misplaced remains zero and the function returns True after the second pass.

If the list contains a single dip, such as [3, 4, 2, 5], the algorithm identifies the violation at the position of 2. Because 2 is not less than the element two steps back (3), the code raises 2 to 4, fixing the sequence in place and allowing the second pass to succeed.

When two separate violations exist, for example [5, 1, 2, 3, 0], the first violation increments misplaced to one and performs a correction. The second violation encountered later increments the counter to two, causing an immediate return of False. This early exit prevents unnecessary work.

The use of extreme sentinel values also protects against inputs that contain the minimum or maximum integer values permissible in the problem domain. Since the sentinels are chosen to be outside the typical range, they never interfere with legitimate comparisons.

Performance Optimizations

Embedding sentinel values eliminates boundary checks inside the loops, allowing direct access to nums[i-2] without conditional guards. This reduces the per-iteration overhead and simplifies the control flow.

The algorithm employs an early-exit strategy in the first pass: as soon as a second disorder is detected, it returns False without completing the remainder of the scan. This prevents wasted iterations on inputs that are already known to be unsalvageable with a single modification.

Modifying the list in place avoids the allocation of auxiliary data structures. The corrective step directly overwrites either nums[i-1] or nums[i], keeping memory usage minimal.

A second pass is required only after the first pass has potentially altered the list. Because the first pass already guarantees that at most one element was changed, the second pass can be a straightforward verification without any additional logic, preserving linear time execution while ensuring correctness.

Imagine a line of numbered blocks that are supposed to be standing in order from smallest to biggest, just like counting toes.

First, the code places a super tiny block at the very start and a super giant block at the very end to act like invisible walls. This helps keep the line tidy.

Then, the code starts walking down the line from left to right. When it finds a block that is smaller than the person behind it, it stops and checks the neighbors. It tries to fix the problem by either nudging that block into a better spot or swapping it with its friend so the line looks orderly again. Because this is tricky, it makes a little note on a piece of paper every time it has to move a block.

If it has to move blocks too many times, the line is just too messy to fix, and the code stops. After that, it takes one last walk down the line to make sure everyone is standing in the perfect order. If it finishes that walk and everyone is in the right spot, the line is ready.

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++	Python	Java					TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java				Go	TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai			Java
	everthis				JS
	fengvyi	C++
	fpdjsns	C++
	halfrost							Go
	haoel		Python
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007		Python
	qiyuangong			Java
	ruoru						Rust
	suxrobGM					C#
	trung-hn		Python
	varunu28			Java
	vthwang			Java
	wisdompeak	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
fpdjsns	C++
halfrost	Go
haoel	Python
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
qiyuangong	Java
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	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