Python3 Program to Modify given array to a non-decreasing array by rotation

Namachila October 13, 2025

0 0 3 minutes read

Given an array arr[] of size N (consisting of duplicates), the task is to check if the given array can be converted to a non-decreasing array by rotating it. If it’s not possible to do so, then print “No“. Otherwise, print “Yes“.

Examples:

Input: arr[] = {3, 4, 5, 1, 2}
Output: Yes
Explanation: After 2 right rotations, the array arr[] modifies to {1, 2, 3, 4, 5}

Input: arr[] = {1, 2, 4, 3}
Output: No

Approach: The idea is based on the fact that a maximum of N distinct arrays can be obtained by rotating the given array and check for each individual rotated array, whether it is non-decreasing or not. Follow the steps below to solve the problem:

Initialize a vector, say v, and copy all the elements of the original array into it.
Sort the vector v.
Traverse the original array and perform the following steps:
- Rotate by 1 in each iteration.
- If the array becomes equal to vector v, print “Yes“. Otherwise, print “No“.

Below is the implementation of the above approach:

Python3

# Python 3 program for the above approach
 
 
# Function to check if a
# non-decreasing array can be obtained
# by rotating the original array
def rotateArray(arr, N):
   
    # Stores copy of original array
    v = arr
 
    # Sort the given vector
    v.sort(reverse = False)
 
    # Traverse the array
    for i in range(1, N + 1, 1):
       
        # Rotate the array by 1
        x = arr[N - 1]
        i = N - 1
        while(i > 0):
            arr[i] = arr[i - 1]
            arr[0] = x
            i -= 1
             
        # If array is sorted
        if (arr == v):
            print("YES")
            return
 
    # If it is not possible to
    # sort the array
    print("NO")
 
# Driver Code
if __name__ == '__main__':
   
    # Given array
    arr =  [3, 4, 5, 1, 2]
 
    # Size of the array
    N = len(arr)
 
    # Function call to check if it is possible
    # to make array non-decreasing by rotating
    rotateArray(arr, N)
     
    # This code is contributed by ipg2016107.

Output

YES

Time Complexity: O(N²)
Auxiliary Space: O(N)

Method 2: Identify the index of the smallest element in the array using the index method, and then creates a rotated version of the array where the smallest element is the first element. It then checks if the rotated array is non-decreasing by traversing through it and comparing each element with the next element.

First, we identify the index of the smallest element in the array using the index method.
We then create a rotated version of the array where the smallest element is the first element. We do this by slicing the original array into two parts and concatenating them in reverse order.
Finally, we traverse through the rotated array and check if it is non-decreasing. If we find an element that is greater than the next element, we return “NO”. Otherwise, we return “YES”.

Implementation:

Python3

def check_rotation(arr):
    n = len(arr)
     
    # Identify the index of the smallest element in the array
    idx = arr.index(min(arr))
     
    # Rotate the array to make the smallest element the first element
    rotated_arr = arr[idx:] + arr[:idx]
     
    # Check if the rotated array is non-decreasing
    for i in range(n-1):
        if rotated_arr[i] > rotated_arr[i+1]:
            return "NO"
     
    return "YES"
 
# Example usage
arr = [3, 4, 5, 1, 2]
result = check_rotation(arr)
print(result) # Output: NO

Output

YES

Time complexity: O(n)
Auxiliary Space: O(n)

Please refer complete article on Modify given array to a non-decreasing array by rotation for more details!

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!