Abstract / Summary

Find the smallest number of right shifts needed to sort an array in non-decreasing order.

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 58% (70k+ 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 Solution class implements a method minimumRightShifts that determines the smallest number of right cyclic shifts required to transform an input list nums into a non-decreasing sequence. If the list cannot be sorted by any number of right shifts, the method returns -1. The algorithm proceeds by locating the minimal element, rotating the list so that this element becomes the first item, verifying the sorted order of the rotated list, and finally computing the shift count based on the original position of the minimal element.

Key Steps

The first step isolates the smallest value in the array and records its index.

low = min(nums)
pos = nums.index(low)

By using the built-in min and index functions, the code obtains both the value and its first occurrence in a single pass each, avoiding explicit loops.

The second step constructs a rotated version of the original list where the smallest element appears at the front. This is achieved through list slicing and concatenation.

shifted = nums[pos:] + nums[:pos]

The third step validates whether the rotated list is already sorted in ascending order. The comparison uses the sorted built-in, which returns a new list sorted in non-decreasing order.

if shifted != sorted(shifted):
    return -1

If the rotated list passes the sorted check, the method determines the required number of right shifts. When the smallest element is already at index 0, no shift is needed and the method returns 0. Otherwise, the number of right shifts equals the length of the list minus the original position of the smallest element.

return 0 if pos == 0 else len(nums) - pos

Edge Cases Handled

When the input list consists of a single element, min returns that element and index yields 0. The rotation step produces a list identical to the original, and the sorted comparison succeeds, leading to a return value of 0. This correctly reflects that no shift is required for a single-element list.

If the smallest element appears multiple times, index selects the first occurrence. Rotating around this first occurrence ensures that any valid right-shift configuration that yields a sorted list will be captured, because a sorted list can only have the minimal value at the beginning. Consequently, cases where duplicate minima are interleaved with larger values are correctly identified as unsortable by right shifts, resulting in -1.

When the list is already sorted in ascending order, the minimal element resides at position 0. The rotation step leaves the list unchanged, the sorted check passes, and the method returns 0, indicating that no shift is necessary.

If the list cannot be sorted by any right shift-such as a descending sequence or a sequence with a “valley” not aligned with the minimal element-the rotated version will differ from its sorted counterpart, and the method returns -1. This behavior correctly captures the impossibility of achieving a sorted order through cyclic right shifts alone.

Performance Considerations

The algorithm leverages Python’s highly optimized built-in functions. The min function scans the list once to locate the smallest value, while index performs a second linear scan to find its first position. The slicing operation nums[pos:] + nums[:pos] creates a new list in linear time, but it avoids element-wise copying inside a loop, benefiting from C-level memory operations.

The sorted comparison uses sorted(shifted), which internally employs Timsort, a hybrid stable sorting algorithm that performs exceptionally well on partially ordered data. In scenarios where the rotated list is already sorted, Timsort detects the existing order and completes with minimal work, effectively reducing overhead for already sorted inputs.

By computing the shift count with a simple arithmetic expression len(nums) - pos, the method avoids iterative counting or additional traversals, delivering the result in constant time after the earlier linear steps.

Overall, the implementation balances clarity with efficient use of Python’s standard library, achieving the desired functionality with a small number of well-optimized operations.

Imagine a row of numbered blocks sitting on a long table. Sometimes these blocks get mixed up, and the goal is to see if they can form a perfect line from smallest to largest just by sliding pieces from the back of the line to the very front.

First, the code looks for the tiniest block in the whole group. It remembers exactly where that tiny block is hiding. Once it finds that spot, it pretends to take all the blocks from that position to the end and moves them to the very front of the line.

After that move, the code checks to see if the row of blocks is perfectly neat and tidy, where every number is smaller than the one that comes after it. If the blocks are not in order, it means it is impossible to fix them this way. If the blocks are already in perfect order before moving anything, it says zero moves are needed. Otherwise, it counts how many blocks were shifted to the front to get them into their happy, tidy line.

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	Java		C++		Python	TS
	WalkCCC	Java		C++		Python
	leetcode.ca	Java		C++	Go	Python	TS
	Progiez	Java		C++		Python
github	charles-wangkai	Java
	fsq			C++
	JoshCrozier		JS
	varunu28	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
varunu28	Java

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