Array Sorted And Rotated

This is problem no #1752 from Leetcode which involves an array and we have to check wether it is sorted and rotated or not. The original problem is as follows: Given an array nums, return true if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return false.

There may be duplicates in the original array.

Note: An array A rotated by x positions results in an array B of the same length such that A[i] == B[(i+x) % A.length], where % is the modulo operation.

The most simple approach to solve this question is to consider a scenario that if our array is sorted in increasing order and is rotated by some steps then in the whole array their has to be only one single point where the next element of the array is smaller than the previous one.

Example: for array [3, 4, 5, 1, 2]

if we loop through this array taking a variable i which starts from i = 1 ; goes till array.length we see ->

1. for i = 1 => arr[1]: 4 > arr[1 - 1]: 3
2. for i = 2 => arr[2]: 5 > arr[2 - 1]: 4
3. for i = 3 => arr[3]: 1 < arr[3 - 1]: 5
4. and for i = 4 => arr[4]: 2 > arr[4 - 1]: 1

so here we can see that their is only one case where the next element is smaller than its previous one. To verify that the array is sorted and rotated we also need to verify one more condition with the above one and that is . The last element of the array has to be smaller than the first element of the array because if the sorted array is rotated at some point then the smaller element must be sent to the last and the larger element must be shifted to the first position.

Check out the simple code snippet

bool sortedAndRotated(vector<int> nums) {
  int count = 0;
  for(int i = 1; i < nums.size(); ++i) {
  if(arr[i] < arr[i - 1]) count ++;
}

if(nums[nums.size() - 1 > nums[0]) count ++;

if(count > 1) return false;
return true;
}

Here we are considering a count variable which if greater than one means our array is not sorted and rotated. Thanks