JavaScript program checks if array can be increased or decreased by rotating it

The rotation of the array refers to assuming that the array is a circular array. Each time the array is rotated, the elements of the array are rotated to the left or right by an index. The elements at one end can be used as the elements at the other end. value. Increasing array means each element will be greater than or equal to its previous element, decreasing array means each element will be less than or equal to the previous element.

In this problem we are given an array and we can rotate the array left or right and we have to find out if we can make the array increase or decrease after a certain rotation (probably zero). p>

Naive method

In this method we will rotate the array and for each rotation we will check whether the current array is increasing or decreasing.

Example

In the following example, we check if the given array can be increased or decreased by rotating it. Below is the input and expected output.

Input: arr = [3, 4, 5, 6, 1, 2]

Expected output: Yes

Input: arr = [5, 1, 6, 2, 5, 3]

Expected output: No

Example

// function to rotate the given array
function rotate(arr){
   var l = 0;
   var r = arr.length-1;
   while(l < r){
      arr[l] += arr[r];
      arr[r] = arr[l]-arr[r];
      arr[l] = arr[l]-arr[r];
      l++;
   }
   return arr;
}

// function to check if the given array is increasing or not
function increasing(arr){

   // getting the size of array
   var len = arr.length
   
   // traversing over the array
   for(var i = 1; i < len; i++){
      if(arr[i] < arr[i-1]){
         return false;
      }
   }
   return true;
}

// function to check if the given array is decreasing or not
function decreasing(arr){

   // getting the size of array
   var len = arr.length
   
   // traversing over the array
   for(var i = 1; i < len; i++){
      if(arr[i] > arr[i-1]){
         return false;
      }
   }
   return true;
}

// function to check whether the given array can become
// increasing or decreasing after certain rotations
function check(arr){
   var k = arr.length
   while(k--){
      if(increasing(arr) || decreasing(arr)){
         return true;
      }
      arr = rotate(arr);
   }
   return false;
}

// defining the arr's
var arr1 = [3, 4, 5, 6, 1, 2]
var arr2 = [5, 1, 6, 2, 5, 3]
console.log("The given array is: ");
console.log(arr1)
if(check(arr1) == true){
   console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
   console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}
console.log("The given array is: ");
console.log(arr2)
if(check(arr2) == true){
   console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
   console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}

Output

The given array is: 
[ 3, 4, 5, 6, 1, 2 ]
Yes, after some rotations given array can be transformed into an increasing or decreasing array
The given array is: 
[ 5, 1, 6, 2, 5, 3 ]
No, after some rotations given array cannot be transformed into an increasing or decreasing array

The time complexity of the above code is O(N*N) and the space complexity is O(1).

Efficient method

In the previous array, we checked whether the array increased or decreased with each rotation, in this method we will partially check the increased or decreased array.

Example

// function to check if the given array is increasing or not
function increasing(arr){

   // getting the size of array
   var len = arr.length
   
   // traversing over the array
   var i = 0;
   for(var i = 1; i < len; i++){
      if(arr[i] < arr[i-1]){
         break;
      }
   }
   if(i == len) return true;
   i++;
   for(; i< len; i++){
      if(arr[i] < arr[i-1]){
         return false;
      }
   }
   return arr[len-1] <= arr[0];
}

// function to check if the given array is decreasing or not
function decreasing(arr){

   // getting the size of array
   var len = arr.length
   
   // traversing over the array
   var i = 0;
   for(var i = 1; i < len; i++){
      if(arr[i] > arr[i-1]){
         break;
      }
   }
   if(i == len) return true;
   i++;
   for(; i< len; i++){
      if(arr[i] > arr[i-1]){
         return false;
      }
   }
   return arr[len-1] >= arr[0];
}

// function to check whether the given array can become increasing or decreasing after certain rotations
function check(arr){
   if(increasing(arr) || decreasing(arr)){
      return true;
   }
   else{
      return false;
   }
}

// defining the arr's
var arr1 = [3, 4, 7, 6, 1, 2]
var arr2 = [5, 1, 6, 2, 5, 3]
console.log("The given array is: ");
console.log(arr1)
if(check(arr1) == true){
   console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
   console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}
console.log("The given array is: ");
console.log(arr2)
if(check(arr2) == true){
   console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
   console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}

Output

The given array is: 
[ 3, 4, 7, 6, 1, 2 ]
No, after some rotations given array cannot be transformed into an increasing or decreasing array
The given array is: 
[ 5, 1, 6, 2, 5, 3 ]
No, after some rotations given array cannot be transformed into an increasing or decreasing array

The time complexity of the above code is O(N) and the space complexity is O(1).

in conclusion

In this tutorial, we implemented a JavaScript program that checks whether a given array can be increased or decreased by rotating it. We implemented two methods with time complexity O(N*N) and O(N), and space complexity both O(1).

The above is the detailed content of JavaScript program checks if array can be increased or decreased by rotating it. For more information, please follow other related articles on the PHP Chinese website!