#2855

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Minimum Right Shifts to Sort the Array

Determine the minimum number of right shifts to sort a distinct integer array or return -1 if impossible using array analysis.

array

Problem Statement

You are given a 0-indexed array nums of length n with distinct positive integers. A right shift moves every element one position to the right, with the last element wrapping to the first position. Return the minimum number of right shifts required to sort nums in ascending order, or -1 if sorting with right shifts is impossible.

For example, for nums = [3,4,5,1,2], after one right shift nums becomes [2,3,4,5,1] and after a second right shift it becomes [1,2,3,4,5], which is sorted. Your task is to compute the minimum number of such right shifts needed to achieve a sorted array.

Examples

Example 1

Input: nums = [3,4,5,1,2]

Output: 2

After the first right shift, nums = [2,3,4,5,1]. After the second right shift, nums = [1,2,3,4,5]. Now nums is sorted; therefore the answer is 2.

Example 2

Input: nums = [1,3,5]

Output: 0

nums is already sorted therefore, the answer is 0.

Example 3

Input: nums = [2,1,4]

Output: -1

It's impossible to sort the array using right shifts.

Constraints

1 <= nums.length <= 100
1 <= nums[i] <= 100
nums contains distinct integers.

Solution Approach

Identify the rotation pivot

Scan the array to find the point where the sequence drops, indicating the rotation pivot. If more than one drop exists, the array cannot be sorted by a single right shift rotation.

Calculate right shifts

Once the pivot is found, compute the number of right shifts needed by measuring how many positions the array must rotate so the pivot element moves to index 0. This gives the minimum right shifts.

Validate sorted order

After computing the shift count, verify that applying the shifts produces a fully sorted array. If validation fails, return -1. This prevents false positives from arrays with multiple breaks.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) to scan for the pivot and validate shifts. Space complexity is O(1) since no extra storage is required beyond counters and indices.

What Interviewers Usually Probe

Checks if candidate identifies the rotation point efficiently.
Observes attention to handling arrays that cannot be sorted by rotation.
Watches for correct calculation of shift counts and validation.

Common Pitfalls or Variants

Common pitfalls

Failing to detect multiple drops in the array causing incorrect shift calculation.
Assuming the array is always sortable by a single rotation.
Off-by-one errors when computing right shift amounts modulo array length.

Follow-up variants

Left shift rotations instead of right shifts with the same pivot logic.
Arrays containing duplicate values requiring careful validation.
Larger arrays requiring efficient O(n) scanning without extra space.

FAQ

What does 'minimum right shifts to sort the array' mean?

It refers to the smallest number of rotations that move each element rightward to achieve ascending order.

Can all arrays be sorted with right shifts?

No, only arrays that form a rotated ascending sequence can be sorted with right shifts; others return -1.

How do I find the pivot efficiently?

Scan the array once to detect where nums[i] > nums[i+1]; this identifies the rotation pivot point.

What is the time complexity of this approach?

O(n) time to locate the pivot and validate the rotation, with O(1) extra space.

How does array-driven solution strategy help here?

It focuses on analyzing the array sequence directly to find breaks and rotations, avoiding unnecessary sorting simulations.

terminal

Solution

Solution 1: Direct Traversal

First, we use a pointer $i$ to traverse the array $nums$ from left to right, finding a continuous increasing sequence until $i$ reaches the end of the array or $nums[i - 1] > nums[i]$. Next, we use another pointer $k$ to traverse the array $nums$ from $i + 1$, finding a continuous increasing sequence until $k$ reaches the end of the array or $nums[k - 1] > nums[k]$ and $nums[k] > nums[0]$. If $k$ reaches the end of the array, it means the array is already increasing, so we return $n - i$; otherwise, we return $-1$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def minimumRightShifts(self, nums: List[int]) -> int:
        n = len(nums)
        i = 1
        while i < n and nums[i - 1] < nums[i]:
            i += 1
        k = i + 1
        while k < n and nums[k - 1] < nums[k] < nums[0]:
            k += 1
        return -1 if k < n else n - i

Continue Practicing

#2856 minimum array length after pair removals #2857 count pairs of points with distance k #2859 sum of values at indices with k set bits