Find Minimum Rotations to Sort an Array in Non-Decreasing Order

Given an array of n integers, you need to find minimum number of below operation such that arrays becomes sorted in non-decreasing order. In a single operation you can rotate the given array clockwise one time. Print -1 if it is not possible to sort the array.

Examples:

Input: {8, 4, 6}
Output: 2
Explanation: 
After applying operation one time, new array becomes - {6, 8, 4}
Again applying the operation leads to array - {4, 6, 8} which is a sorted array.

Input: {2, 4, 3}
Output: -1 
Explanation: 
It is not possible to sort this array using above operation.

Approach:

We traverse left to right and find first index such that the elements are in decreasing order.
Now we traverse the given array starting from the index found from above step by using modulo operator. Now if we find any index such that elements are in decreasing order, then we print -1 as it is not possible to sort the array now. Else we return N(Length of array) – i (index found from step 1)

Below is the implementation for above approach:

C++

// CPP implementation for above approach
#include <iostream>
using namespace std;

int main()
{
    int n = 3;
    int a[] = { 8, 4, 6 };

    int c = -1;
    for (int i = 0; i < n - 1; i++) {
        // Finding first index where our array
        // is not sorted
        if (a[i] > a[i + 1]) {
            c = i + 1;
            break;
        }
    }

    if (c == -1) {
        // If the given array is sorted, we print 0
        cout << "0";
        return 0;
    }

    for (int i = 0; i < n - 1; i++) {
        // Traversing the whole array from index c to
        // find if there is another index such that array
        // is not sorted
        if (a[(c + i) % n] > a[(c + i + 1) % n]) {
            cout << "-1";
            return 0;
        }
    }

    // Print number of operations required
    cout << n - c;
    return 0;
}

Java

// Java implementation for above approach
import java.io.*;

public class Cpp {
    // Driver code
    public static void main(String[] args)
    {
        int n = 3;
        int[] a = new int[] { 8, 4, 6 };
      
        int c = -1;
        for (int i = 0; i < n - 1; i++) {
            // Finding first index where our array
            // is not sorted
            if (a[i] > a[i + 1]) {
                c = i + 1;
                break;
            }
        }
      
        if (c == -1) {
            // If the given array is sorted, we print 0
            System.out.println("0");
            return;
        }
      
        for (int i = 0; i < n - 1; i++) {
            // Traversing the whole array from index c to
            // find if there is another index such that array
            // is not sorted
            if (a[(c + i) % n] > a[(c + i + 1) % n]) {
                System.out.println("-1");
                return;
            }
        }
      
        // Print number of operations required
        System.out.println(n - c);
    }
}

Output:

Time complexity: O(n), where n is the size of given array
Space complexity: O(1)

Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.