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 arraydef 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 Codeif __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. |
YES
Time Complexity: O(N2)
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 usagearr = [3, 4, 5, 1, 2]result = check_rotation(arr)print(result) # Output: NO |
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
