1752. Check if Array Is Sorted and Rotated

#array

Check if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero).

---

Intuition

If the array is sorted then it will have 0 inversion, if a sorted array is rotated either clockwise or anti-clockwise direction the amount of inversion will be 1.

[1,2,3,4,5,6,7,8,9] => rotate clockwise 3 time => [7,8,9,1,2,3,4,5,6]
[1,2,3,4,5,6,7,8,9] => rotate anti-clockwise 3 time => [4,5,6,7,8,9,1,2,3]

In a sorted or rotated-sorted array, there can be at most one "drop" (i.e., an instance where an element is greater than its immediate successor). By checking for these drops, we can conclude whether the array satisfies the condition.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(n)$

Code

public boolean check(int[] nums) {
    // if the array is sorted the next immediate will always be larger
    // except at the point of rotation    
    int countInversion = 0;
    for (int i = 0; i < nums.length; ++i) {
        if( nums[i] > nums[ (i+1)%nums.length ] ) countInversion++; 
    }    
    return countInversion <= 1 ;
}