Minimum Right Shifts to Sort the Array

Minimum Right Shifts to Sort the Array - Problem

Array Easy

You are given a 0-indexed array nums of length n containing distinct positive integers. Return the minimum number of right shifts required to sort nums and -1 if this is not possible.

A right shift is defined as shifting the element at index i to index (i + 1) % n, for all indices.

In other words, a right shift moves all elements one position to the right, with the last element wrapping around to the first position.

Input & Output

Example 1 — Rotated Sorted Array

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

› Output: 2

💡 Note: Array is rotated sorted. Break point at index 2 (5>1). Need 5-(2+1)=2 right shifts to get [1,2,3,4,5]

Example 2 — Already Sorted

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

› Output: 0

💡 Note: Array is already sorted, no break points found. Need 0 shifts

Example 3 — Impossible Case

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

› Output: -1

💡 Note: Multiple break points: 2>1 and 4>2 (wraparound). Cannot be sorted by rotation

Constraints

1 ≤ nums.length ≤ 100
1 ≤ nums[i] ≤ 100
nums contains distinct values

Visualization

Tap to expand

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that a rotated sorted array has exactly one break point where a larger element precedes a smaller one. The optimal approach finds this break point in O(n) time and calculates the required shifts. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Find Break Point	O(n)	O(1)	Find where the sorted order breaks and check if it's a valid rotation point
Brute Force - Try All Rotations	O(n²)	O(n)	Try every possible number of right shifts and check if array becomes sorted

Optimized - Find Break Point — Algorithm Steps

Step 1: Count break points where nums[i] > nums[i+1]
Step 2: If more than 1 break point, return -1
Step 3: If 0 break points, array is already sorted
Step 4: If 1 break point, calculate required shifts

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Array

Look for positions where nums[i] > nums[i+1]

Found Break

At index 2: 5 > 1 (break point found)

Calculate

Need n - (break_index + 1) = 5 - 3 = 2 shifts

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int n) {
    if (n <= 1) return 0;
    
    // Count break points where nums[i] > nums[i+1]
    int breakCount = 0;
    int breakIndex = -1;
    
    for (int i = 0; i < n; i++) {
        if (nums[i] > nums[(i + 1) % n]) {
            breakCount++;
            breakIndex = i;
        }
    }
    
    // If more than 1 break point, impossible to sort
    if (breakCount > 1) {
        return -1;
    }
    
    // If no break points, already sorted
    if (breakCount == 0) {
        return 0;
    }
    
    // One break point found
    return n - ((breakIndex + 1) % n);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[100];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to count break points

✓ Linear Growth

Space Complexity

O(1)

Only use constant extra variables

✓ Linear Space

24.5K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Find Break Point — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler