LeetCode 2855 - Minimum Right Shifts to Sort the Array

LeetCode Problem 2855

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem gives us a 0-indexed array nums of length n containing distinct positive integers. The goal is to determine the minimum number of right shifts required to sort the array in strictly increasing order. A right shift moves each element at index i to (i + 1) % n, effectively rotating the array one step to the right, with the last element wrapping around to the first position. If it is impossible to sort the array using any number of right shifts, the function should return -1.

The constraints guarantee that 1 <= nums.length <= 100, which is small enough to allow algorithms with O(n) or O(n^2) complexity. Since the integers are distinct, we do not need to handle duplicates, which simplifies the determination of a sorted sequence. Edge cases to consider include arrays that are already sorted, arrays that require a full rotation, and arrays where no amount of shifting will yield a sorted array.

Approaches

The naive brute-force approach would simulate right-shifting the array step by step, checking after each shift if the array is sorted. This approach is correct but inefficient, especially if n is close to 100, since it could require up to n rotations with O(n) work per rotation, yielding O(n^2) complexity.

The optimal approach leverages the insight that a right shift effectively rotates the array. If the array can be sorted with right shifts, it must be a rotated version of a sorted array. By identifying the "pivot" or the point where the order breaks (where an element is greater than the next element), we can determine the minimum shifts. If there is more than one break point, sorting by rotation is impossible. The minimum number of right shifts is then n - pivot_index - 1.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Simulate each right shift and check if array is sorted
Optimal	O(n)	O(1)	Find the single rotation point and compute shifts directly

Algorithm Walkthrough

1. Initialize a counter for the number of "breaks" in the sorted order. A break occurs where nums[i] > nums[i+1].
2. Iterate through the array from index 0 to n-1. Compare nums[i] with nums[(i+1) % n] to account for the wrap-around.
3. Record the index where a break occurs. If more than one break is found, return -1 because the array cannot be sorted by right shifts.
4. If no break is found, the array is already sorted, so return 0.
5. If exactly one break is found at index i, the minimum right shifts needed is n - i - 1, since performing that many right shifts will place the smallest element at the first index.
6. Return the computed shift count.

Why it works: The algorithm relies on the property that a right shift rotates the array. If the array is sortable by rotations, there must be at most one point where the order decreases; otherwise, no sequence of rotations will produce a sorted array. The formula n - break_index - 1 guarantees that the smallest element moves to the front, restoring the sorted order.

Python Solution

from typing import List

class Solution:
    def minimumRightShifts(self, nums: List[int]) -> int:
        n = len(nums)
        break_index = -1
        
        for i in range(n):
            if nums[i] > nums[(i + 1) % n]:
                if break_index != -1:
                    return -1
                break_index = i
        
        if break_index == -1:
            return 0
        
        return n - break_index - 1

In the implementation, break_index keeps track of the position where the array order is violated. Iteration through 0 to n-1 allows us to detect order violations efficiently. If no violation exists, the array is sorted. If exactly one violation exists, the formula computes the minimum right shifts required. Multiple violations indicate sorting by rotation is impossible.

Go Solution

func minimumRightShifts(nums []int) int {
    n := len(nums)
    breakIndex := -1
    
    for i := 0; i < n; i++ {
        next := (i + 1) % n
        if nums[i] > nums[next] {
            if breakIndex != -1 {
                return -1
            }
            breakIndex = i
        }
    }
    
    if breakIndex == -1 {
        return 0
    }
    
    return n - breakIndex - 1
}

The Go implementation mirrors the Python logic. The main difference is that Go requires explicit variable declaration and uses % to handle wrap-around indexing.

Worked Examples

Example 1: [3, 4, 5, 1, 2]

i	nums[i]	nums[(i+1)%n]	break?	break_index
0	3	4	No	-1
1	4	5	No	-1
2	5	1	Yes	2
3	1	2	No	2
4	2	3	No	2

One break at index 2 → shifts = 5 - 2 - 1 = 2.

Example 2: [1, 3, 5]

No breaks → already sorted → shifts = 0.

Example 3: [2, 1, 4]

i	nums[i]	nums[(i+1)%n]	break?	break_index
0	2	1	Yes	0
1	1	4	No	0
2	4	2	Yes	multiple

Multiple breaks → impossible → return -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array to detect breaks
Space	O(1)	Constant space for tracking break_index

The linear time complexity is optimal since each element must be checked at least once. Constant space is sufficient because only a single index needs to be tracked.

Test Cases

# Provided examples
assert Solution().minimumRightShifts([3,4,5,1,2]) == 2  # standard rotation case
assert Solution().minimumRightShifts([1,3,5]) == 0      # already sorted
assert Solution().minimumRightShifts([2,1,4]) == -1     # impossible

# Edge and additional cases
assert Solution().minimumRightShifts([1]) == 0          # single element
assert Solution().minimumRightShifts([2,1]) == 1        # simple two-element swap
assert Solution().minimumRightShifts([4,5,1,2,3]) == 3  # full rotation
assert Solution().minimumRightShifts([1,2,3,4,5]) == 0  # already sorted, no shifts

Test	Why
[3,4,5,1,2]	Tests standard rotation with one break
[1,3,5]	Tests already sorted array
[2,1,4]	Tests impossible rotation (multiple breaks)
[1]	Edge case, single element
[2,1]	Minimal array needing one shift
[4,5,1,2,3]	Tests larger array requiring rotation
[1,2,3,4,5]	Already sorted, zero shifts

Edge Cases

One important edge case is an array with a single element. Since a single element is trivially sorted, the algorithm correctly returns 0. Another case is a two-element array that is reversed. The algorithm correctly detects the single break and calculates one shift. A third edge case is an array with multiple breaks, which occurs when the rotation cannot produce a sorted array. For instance, [2,1,4] has two order violations, and the algorithm immediately returns -1 without unnecessary computations. These cases ensure the implementation handles minimal input, maximal simplicity, and unsortable rotations correctly.