Abstract / Summary

Check if the array is sorted in non-decreasing order or can become sorted by rotating it once.

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 57% (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 presented implementation defines a class with a single method that determines whether a given integer array can be interpreted as a rotated version of a non-decreasing sequence. The method iterates through the array to locate the first point where the ordering property is violated. When such a point is found, the code reconstructs the array as if it were rotated back to its original sorted orientation and then checks whether this reconstructed array is sorted. If no violation is encountered during the scan, the method concludes that the input is already sorted and returns true.

Key Steps

The first logical block establishes a linear scan that starts at the second element and compares each element with its immediate predecessor.

for i in range(1, len(nums)):
    if nums[i] < nums[i - 1]:
        # rotation point detected

When the condition nums[i] < nums[i - 1] becomes true, the index i is treated as the rotation pivot. The next step creates a new list that places the segment starting at the pivot at the front, followed by the preceding segment.

unrotated = nums[i:] + nums[:i]

The final verification step compares the reconstructed list with its sorted counterpart, returning the boolean result of that equality test.

return unrotated == sorted(unrotated)

If the loop completes without finding any decreasing pair, the method reaches the concluding statement that declares the input already satisfies the required property.

return True

Edge Cases Handled

The algorithm gracefully handles an empty list or a list containing a single element. In both situations the range in the loop evaluates to an empty sequence, causing the loop body to be skipped and the method to return true, which is appropriate because a trivial list is inherently a rotated sorted sequence.

When the input list is already sorted in non-decreasing order, the loop never encounters a decreasing pair, and the method returns true without performing any additional work.

If the list consists of repeated values, the comparison nums[i] < nums[i - 1] does not trigger on equal elements, so the algorithm treats a uniform list as already sorted and returns true.

In the scenario where the rotation point occurs at the very first element (i.e., the list is a proper rotation of a sorted sequence), the first decreasing pair will be detected at the index where the wrap-around occurs, and the reconstruction step will correctly reorder the list for the sorted check.

Performance Optimizations

The implementation leverages early exit by returning immediately after the first rotation point is identified and verified. This prevents unnecessary scanning of the remainder of the array once the decisive information is available.

The reconstruction of the unrotated list uses Python’s slice concatenation, which creates a new list in a single operation rather than building it element by element. This approach benefits from the underlying C-level optimizations of slice handling.

The final equality check compares the reconstructed list with the result of sorted(unrotated). Because sorted returns a new list, the comparison can short-circuit as soon as a mismatching element is found, avoiding a full element-wise scan in many cases where the rotation does not produce a sorted order.

Overall, the method performs a single pass over the input until a rotation point is found, followed by at most one additional pass for sorting and comparison, which aligns with an efficient handling of typical input sizes.

Imagine you have a long train of colored blocks lined up on the floor. Each block has a number painted on it. This code looks at those blocks one by one to see if they are in the right order from smallest to biggest.

Sometimes, people take a train of blocks and pick it up from the middle to move the back part to the front. This is called rotating the train. The code checks if the blocks might have been shifted like that. First, it walks down the line of blocks looking for a spot where a number is smaller than the one that came before it. If it finds such a spot, it mentally picks up the train and puts the back part in front, just like swapping the ends of the line. After moving those parts, the code arranges the blocks in a straight line and checks if they end up perfectly sorted from smallest to biggest. If the blocks are already in order or if moving the end makes them line up correctly, the code says everything is in the right place.

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++			Java
	leetcode.ca	C++	Python		Java		Go			C	Rust	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim									C
	everthis			JS
	fartem					Ruby
	fsq	C++
	halfrost						Go
	haoel	C++
	JoshCrozier			JS
	Krazune	C++
	lkwq007		Python
	Shamik07							Dart
	suxrobGM								C#
	trung-hn		Python
	varunu28				Java
	wisdompeak	C++
	withaarzoo	C++
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C, C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fsq	C++
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
Krazune	C++
lkwq007	Python
Shamik07	Dart
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
withaarzoo	C++
YuriSpiridonov	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