1752. Check if Array Is Sorted and Rotated¶
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 ;
}