Intuition

To check whether we are dealing with a rotated sorted list or not, we could sort the list, test all possible combinations, and then if we find one that works, we know the list was sorted. However, there is a solution that does not require sorting the list.

Approach

If a list $L$ is sorted, then it must always hold that $\forall j <= k,\; L[j]<= L[k]$. For example, $L=[1, 2, 3, 4, 5]$ is a sorted list.

If we rotate $L$ to create a new list $RL$, whether we do it clockwise or anticlockwise, what happens is that the previous condition is always true on $RL$, except when we have the “jump” from the maximum value to the lowest one. For example,

Hence, we can test this on the input list. If we find more than one exception of this type, then we know we are not dealing with a rotated version of a sorted list.

This is not sufficient to verify that the list is indeed a rotated sorted list, test was happens for $L = [3, 4, 6, 5, 7]$. This list is not a sorted rotated list, however:

• there is only one exception, the jump from 6 to 5, and;
• in all other cases, when we take two contiguous values, the value at the right is larger that the one in the left.

What are we missing? Looking at $RL_1$ and $RL_2$, we can infer another necessary condition which we had not yet considered: if we create a list $LR$ with the values to the right of the exception, and tried to insert them in a list $LL$ conformed by the values to the right of the exeception, we could just merge the right list with the left list.

In practice, do we need to insert the values? Not really, we can continue reasoning. Taking any element $x$ from $LR$, $x$ should always get inserted on the first position of $LL$. For this to happen, it should always be true that $x <= LL[0]$. If this does not hold for any of the elements of $LR$, then we can confidently say that the list is not a rotated sorted list.

At this point, there only some details to consider:

1. We only need to test $\forall x \in LR, \;x <= LL[0]$ if there is an exception. If there are no exceptions, the lists $LL$ and $LR$ conceptually do not exist, we just need to verify that the list is always increasing.
2. If there is an exception, we can try to speed up the algorithm by testing $LR[end] <= LL[0]$. Since $\forall x \in LR, \;x <= LL[0]$, then this must hold in particular for the last element of $LR$. We look ahead because if $LR$ would be sorted, the last element would be the maximum, and thus comparing directly against this value, we could save the time to traverse $LR$ to confirm that it is indeed sorted.
3. Note that there can be repeated elements on the input array, that is why the conditions are checking for values greater or less than another in a strick way, otherwise we should use $\geq$ and $\leq$
4. If the list has at most 2 elements, we don’t have much to do: for 1 element, there are no possible rotations, and with 2 elements the list is sorted either incresingly or decreasingly, so it always is a rotated sorted list.

Complexity

• Time complexity: $O(n)$ as in the worst scenario, we need to traverse all the list to ensure that the provided input is a circular permutation of the sorted list.

• Space complexity: $O(1)$ as the space taken by the variables we use is not proportional to the length of the input list.

Code

```python [] class Solution(object): def check(self, nums): “”” :type nums: List[int] :rtype: bool “”” n = len(nums)

    if n == 1 or n == 2:
        return True
        
    has_exceptions = False

    for i in range(n - 1):
        left = nums[i]
        right = nums[i + 1]

        if right < left:
            if has_exceptions:
                return False

            if nums[n - 1] > nums[0]:
                return False
            
            has_exceptions = True

        if has_exceptions and right > nums[0]:
            return False

    return True   

class Solution(object): def check(self, nums): “”” :type nums: List[int] :rtype: bool “”” n = len(nums)

    if n == 1 or n == 2:
        return True

    for i in range(n - 1):
        if nums[i + 1] < nums[i]:
            break
    else:
        return True

    if nums[n - 1] > nums[0]:
        return False

    for j in range(i + 1, n - 1):
        if nums[j + 1] < nums[j]:
            return False

        if nums[j] > nums[0]:
            return False

    return True              ```