Problem Statement in English

You are given an array nums that is sorted in non-decreasing order and then rotated at an unknown pivot index.

Return true if the array is sorted and rotated, and false otherwise. Even if there are duplicates in the array, it is still considered sorted and rotated. 0 rotations are also allowed.

Approach

We just need to check if there is more than one drop in the array. A drop is when nums[i] > nums[i + 1]. If there is more than one drop, then the array is not sorted and rotated.

We can check if the next index - circularly - is smaller than the current index. If it is, then we have a drop. We can count the number of drops and if it is more than 1, we return false. Otherwise, we return true.

Solution in Python


class Solution:
    def check(self, nums: List[int]) -> bool:
        drops = 0
        n = len(nums)
        
        for i in range(n):
            if nums[i] > nums[(i + 1) % n]:
                drops += 1
                
            if drops > 1:
                return False
                
        return True

Complexity

  • Time: $O(n)$
    Since we need to iterate through the array once to count the number of drops.

  • Space: $O(1)$
    We are using only a constant amount of extra space to store the count of drops and the length of the array.

Mistakes I Made

I overcomplicated the problem and the code aghhh :(

And we are done.