Check if it is possible to make array increasing or decreasing by rotating it

In this post we will write a C++ program to check if it is possible to make an array increasing or decreasing by rotating the array.

Given: An array arr[] of N distinct elements.

Problem: To check if it is possible to make it increasing or decreasing by rotating the array in any direction.

Examples:

Input: arr[] = {6, 2, 4, 3, 5}
Output: Yes
Array can be rotated as {2, 3, 4, 5, 6}

Input: arr[] = {4, 5, 6, 7, 8}
Output: No

Solution:

There are 4 conditions possible in this case:

1. If the array is already increasing then the result is Yes.
2. If the array is already decreasing then the result is Yes.
3. If the given array is first increasing up to the maximum element and then decreasing, then the array can be made increasing.
4. If the given array is first decreasing up to the minimum element and then increasing, then the array can be made decreasing.
5. If it is not possible to make the array increasing or decreasing then result is No.

Now let’s implement the same in programming code:

Implementation in C++:

#include <bits/stdc++.h> 
using namespace std; 

// Function that returns true if the array 
// can be made increasing or decreasing 
// after rotating it in any direction 
bool isPossible(int a[], int n) 
{ 
    // If size of the array is less than 3 
    if (n <= 2) 
        return true; 

    int flag = 0; 
    // Check if the array is already decreasing 
    for (int i = 0; i < n - 2; i++) { 
        if (!(a[i] > a[i + 1] and a[i + 1] > a[i + 2])) { 
            flag = 1; 
            break; 
        } 
    } 

    // If the array is already decreasing 
    if (flag == 0) 
        return true; 

    flag = 0; 
    // Check if the array is already increasing 
    for (int i = 0; i < n - 2; i++) { 
        if (!(a[i] < a[i + 1] and a[i + 1] < a[i + 2])) { 
            flag = 1; 
            break; 
        } 
    } 

    // If the array is already increasing 
    if (flag == 0) 
        return true; 

    // Find the indices of the minimum 
    // and the maximum value 
    int val1 = INT_MAX, mini = -1, val2 = INT_MIN, maxi; 
    for (int i = 0; i < n; i++) { 
        if (a[i] < val1) { 
            mini = i; 
            val1 = a[i]; 
        } 
        if (a[i] > val2) { 
            maxi = i; 
            val2 = a[i]; 
        } 
    } 

    flag = 1; 
    // Check if we can make array increasing 
    for (int i = 0; i < maxi; i++) { 
        if (a[i] > a[i + 1]) { 
            flag = 0; 
            break; 
        } 
    } 

    // If the array is increasing upto max index 
    // and minimum element is right to maximum 
    if (flag == 1 and maxi + 1 == mini) { 
        flag = 1; 
        // Check if array increasing again or not 
        for (int i = mini; i < n - 1; i++) { 
            if (a[i] > a[i + 1]) { 
                flag = 0; 
                break; 
            } 
        } 
        if (flag == 1) 
            return true; 
    } 

    flag = 1; 
    // Check if we can make array decreasing 
    for (int i = 0; i < mini; i++) { 
        if (a[i] < a[i + 1]) { 
            flag = 0; 
            break; 
        } 
    } 

    // If the array is decreasing upto min index 
    // and minimum element is left to maximum 
    if (flag == 1 and maxi - 1 == mini) { 
        flag = 1; 

        // Check if array decreasing again or not 
        for (int i = maxi; i < n - 1; i++) { 
            if (a[i] < a[i + 1]) { 
                flag = 0; 
                break; 
            } 
        } 
        if (flag == 1) 
            return true; 
    } 

    return false; 
} 

int main() 
{ 
    int a[] = { 4, 5, 6, 2, 3 }; 
    int n = sizeof(a) / sizeof(a[0]); 

    if (isPossible(a, n)) 
        cout << "Yes"; 
    else
        cout << "No"; 

    return 0; 
} 

Comment below in case of any suggestion or discuss the same.