Today’s problem

https://leetcode.com/problems/check-if-array-is-sorted-and-rotated/description/

Intuition

If it is shifted, then it must contain a full original list if we concate two nums together.

Trick

Append the original list to the back of itself it is somehow a ring.

Approach

• Concat nums at the end of itself.
• Then test whether there are at least N non decreasing numbers.

Complexity

• Time complexity: $O(N)$, N is the length of the array

• Space complexity: $O(1)$

Code

class Solution:
    def check(self, nums: List[int]) -> bool:
        n = len(nums)
        nums += nums
        cnt = 1
        pre = nums[0]
        for num in nums[1::]:
            if num >= pre:
                cnt += 1
            else:
                cnt = 1
            pre = num

            if cnt >= n:
                return True
        

        return False