JavaScript program: check if array is sorted and rotate it

A sorted array is an array in which all elements are arranged in ascending order. We are given an array of size N and an array containing distinct integers (meaning each integer appears only once). We have to check if the array is sorted and rotated in clockwise direction. Here, if the array is sorted and rotated, we must return "YES", otherwise, we must return "NO".

Note - Here we are talking about sorting and rotation meaning there should be at least one rotation. We cannot treat a sorted array as a sorted and rotated array.

Suppose we have been given an array of size N

enter

N = 5
Array = [5, 1, 2, 3, 4]

Output

Yes, the given array is sorted and rotated. 

illustrate

The array is sorted and rotated by 1 bit

Sorted array = [1, 2, 3, 4, 5]
Rotated above sorted array by 1 place, we get = [5, 1, 2, 3, 4]

The array sorted by 1 position and rotated matches the input array, so the output is "yes".

enter

N = 6
Array = [6, 5, 1, 2, 3, 4]

Output

No, the given array is not sorted and rotated array. 

illustrate

The given array is an unsorted and rotated array

Sorted array = [1, 2, 3, 4, 5, 6]
Rotated above sorted array by 1 place, we get = [6, 1, 2, 3, 4, 5]
Rotated above sorted array by 2 place, we get = [5, 6, 1, 2, 3, 4]
Rotated above sorted array by 3 place, we get = [4, 5, 6, 1, 2, 3]
Rotated above sorted array by 4 place, we get = [3, 4, 5, 6, 1, 2]
Rotated above sorted array by 5 place, we get = [2, 3, 4, 5, 6, 1]

Neither the sorted nor rotated arrays above match the input array, so the answer is, no.

method

Here we will discuss two methods. Let us see them in the following sections -

Method 1: Check if the array is sorted and rotated by finding the pivot element (minimum number)

The idea of ​​this method is that we will find the minimum number and if our array is sorted and rotated, the values ​​before and after the minimum number should be in a sorted manner.

Example

// function to check if the given array is sorted and rotated 
function check(arr){
   var len = arr.length;
   var mi = Number.MAX_VALUE; // variable to find the smallest number 
   var idx_min = -1; // variable to store the index of smallest number;
   
   // traversing over the array to find the minimum element and its index
   for(var i = 0; i < len; i++){
      if (arr[i] < mi){
         mi = arr[i];
         idx_min = i;
      }
   }
   
   // traversing over the array to find that all the elements 
   // before the minimum element are sorted 
   for(var i = 1; i < idx_min; i++){
      if (arr[i] < arr[i - 1]){
         return false;
      }
   }
   
   // traversing over the array to find that all the elements after the minimum element are sorted 
   for(var i = idx_min + 1; i < len; i++){
      if (arr[i] < arr[i - 1]){
         return false;
      }
   }
   
   // checking if the last element of the array is smaller than the first element or not 
   if(arr[len-1] > arr[0]){
      return false;
   }
   else{
      return true;
   }
}

// defining the array 
var arr = [5, 1, 2, 3, 4];
console.log("The given array is: ")
console.log(arr);

// calling to the function
if(check(arr)){
   console.log("Yes, the given array is sorted and rotated");
}
else{
   console.log("No, the given array is not sorted and rotated array")
}

Time complexity - O(N), where N is the size of the array.

Space Complexity - O(1) since we are not using any extra space.

Method 2: Check if the array is sorted and rotated by calculating adjacent inversions

The idea of ​​this method is that we will iterate through the array and check if the previous element is smaller than the current element. For a sorted and rotated array, the count must be 1 if the previous element is greater than the current element, otherwise the array is not sorted and rotated.

Example

// function to check if the given array is sorted and rotated 
function check(arr){
   var len = arr.length;
   var count = 0; // variable to count the adjacent inversions
   
   // traversing over the array to find the number of times first element is smaller than second 
   for(var i = 1; i < len; i++){
      if (arr[i] < arr[i-1]){
         count++;
      }
   }
   
   // checking if the last element of the array is smaller 
   // than the first element or not and inversion must be equal to 1
   if(arr[len-1] > arr[0] || count != 1){
      return false;
   }
   else{
      return true;
   }
}

// defining the array 
var arr = [5, 1, 2, 3, 4];
console.log("The given array is: ")
console.log(arr);

// calling to the function
if(check(arr)){
   console.log("Yes, the given array is sorted and rotated");
}
else{
   console.log("No, the given array is not sorted and rotated array")
}

Time complexity - O(N), where N is the size of the array.

Space Complexity - O(1) since we are not using any extra space.

in conclusion

In this tutorial, we discussed how to check if an array is sorted and rotated. Here we see two methods, the first is to find the pivot (which means the smallest element) and the other is by calculating adjacent inversions. The time and space complexity of both methods are the same, i.e. O(N) and O(1) respectively.

The above is the detailed content of JavaScript program: check if array is sorted and rotate it. For more information, please follow other related articles on the PHP Chinese website!