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

0 0 3 minutes read

Given an array arr[] of N distinct elements, the task is to check if it is possible to make the array increasing or decreasing by rotating the array in any direction.
Examples:

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

Approach: There are four possibilities:

If the array is already increasing then the answer is Yes.
If the array is already decreasing then the answer is Yes.
If the array can be made increasing, this can be possible if the given array is first increasing up to the maximum element and then decreasing.
If the array can be made decreasing, this can be possible if the given array is first decreasing up to the minimum element and then increasing.

If it is not possible to make the array increasing or decreasing then print No.
Below is the implementation of the above approach:

Javascript

<script>
// javascript implementation of the approach    
// Function that returns true if the array
    // can be made increasing or decreasing
    // after rotating it in any direction
    function isPossible(a , n) {
        // If size of the array is less than 3
        if (n <= 2)
            return true;
 
        var flag = 0;
 
        // Check if the array is already decreasing
        for (i = 0; i < n - 2; i++) {
            if (!(a[i] > a[i + 1] && 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 (i = 0; i < n - 2; i++) {
            if (!(a[i] < a[i + 1] && 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
        // && the maximum value
        var val1 = Number.MAX_VALUE, mini = -1, val2 = Number.MIN_VALUE, maxi = 0;
        for (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 (i = 0; i < maxi; i++) {
            if (a[i] > a[i + 1]) {
                flag = 0;
                break;
            }
        }
 
        // If the array is increasing upto max index
        // && minimum element is right to maximum
        if (flag == 1 && maxi + 1 == mini) {
            flag = 1;
 
            // Check if array increasing again or not
            for (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 (i = 0; i < mini; i++) {
            if (a[i] < a[i + 1]) {
                flag = 0;
                break;
            }
        }
 
        // If the array is decreasing upto min index
        // && minimum element is left to maximum
        if (flag == 1 && maxi - 1 == mini) {
            flag = 1;
 
            // Check if array decreasing again or not
            for (i = maxi; i < n - 1; i++) {
                if (a[i] < a[i + 1]) {
                    flag = 0;
                    break;
                }
            }
            if (flag == 1)
                return true;
        }
 
        // If it is not possible to make the
        // array increasing or decreasing
        return false;
    }
 
    // Driver code
     
        var a = [ 4, 5, 6, 2, 3 ];
        var n = a.length;
 
        if (isPossible(a, n))
            document.write("Yes");
        else
            document.write("No");
 
// This code contributed by umadevi9616
</script>

Output:

Yes

Time Complexity: O(n)

Auxiliary Space: O(1)

Please refer complete article on Check if it is possible to make array increasing or decreasing by rotating the array 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!