Check if Array Is Sorted and Rotated

How it works

In a sorted-and-rotated array, there can be at most one "break point" where a larger element is followed by a smaller element. This break point is where the rotation occurred. If we find more than one such break, the array cannot be a valid rotation of a sorted array.

Steps

1. Initialize a counter for the number of break points (where an element is greater than its next element).
2. Iterate through the array, comparing each element with the next one (using modulo to wrap around from the last element to the first).
3. If the current element is greater than the next element, increment the break counter.
4. If the counter exceeds 1 at any point, return false immediately.
5. After checking all pairs, return true (at most one break was found).

Complexity

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

Things to watch for

Forgetting to Check the Wrap-Around

A sorted and rotated array is circular, so you must compare the last element with the first element. Using nums[i] > nums[i + 1] without modulo wrapping misses the case where the "break" occurs between the last and first elements.

Expecting Strictly Increasing Order

The problem allows non-decreasing order (duplicates are permitted). Checking for strict inequality nums[i] >= nums[i+1] instead of nums[i] > nums[i+1] incorrectly flags valid arrays like [1, 1, 1] or [2, 2, 3, 1, 1] as invalid.

from typing import List

class Solution:
    def check(self, nums: List[int]) -> bool:
        count, N = 0, len(nums)

        for i in range(N):
            if nums[i] > nums[(i + 1) % N]:
                count += 1
                if count > 1:
                    return False

        return True

class Solution {
public:
    bool check(vector<int>& nums) {
        int count = 0, N = nums.size();

        for (int i = 0; i < N; i++) {
            if (nums[i] > nums[(i + 1) % N] && ++count > 1) {
                return false;
            }
        }

        return true;
    }
};