Check if Array Is Sorted and Rotated

main.md

Question

Approach

I approached the problem by iterating through the array and compare each element with its next neighbor. I then compare the last element with the first.

As I iterate, every time I encounter a situation where the current element is greater than the next, I increase a counter. If this counter exceeds one, I immediately know the array couldn’t have come from a sorted array that was simply rotated, and I return false. If I complete the loop and find one or no drops, I return true.

Implementation

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

Complexities

• Time: O(n).
• Space: O(1).