1752. Check if Array Is Sorted and Rotated - Explanation

1. Brute Force

Intuition

A sorted and rotated array can be thought of as taking a sorted array and moving some elements from the end to the beginning. For example, [3,4,5,1,2] is [1,2,3,4,5] rotated. We can verify this by sorting the array and checking if our original array matches some rotation of the sorted version.

Algorithm

Create a sorted copy of the input array.
Try every possible rotation (0 to n-1 positions).
For each rotation amount i, compare the original array with the sorted array rotated by i positions.
To compare, check elements from position n-i to n-1 of the sorted array against the beginning of the original, then elements from position 0 to n-i-1 against the rest.
If any rotation matches the original array, return true.
If no rotation matches, return false.

class Solution:
    def check(self, nums: List[int]) -> bool:
        sortedNums = sorted(nums)
        arr = []

        for i in range(len(nums)):
            arr.insert(0, sortedNums.pop())
            if nums == arr + sortedNums:
                return True

        return False

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Sliding Window

Intuition

If we imagine the array as circular (the last element connects back to the first), a valid sorted-and-rotated array should have a contiguous segment of length n where elements are in non-decreasing order. We can simulate this circular behavior by conceptually doubling the array and looking for n consecutive non-decreasing elements.

Algorithm

Iterate through indices 1 to 2n-1, treating the array as circular using modulo operations.
Maintain a count of consecutive non-decreasing pairs.
If the current element (at index i % n) is greater than or equal to the previous element, increment the count.
Otherwise, reset the count to 1.
If at any point the count reaches n, we found a valid sorted sequence, so return true.
Handle the edge case where n equals 1 by returning true at the end.

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

        for i in range(1, 2 * N):
            if nums[(i - 1) % N] <= nums[i % N]:
                count += 1
            else:
                count = 1
            if count == N:
                return True

        return N == 1

Time & Space Complexity

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

3. Iteration

Intuition

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.

Algorithm

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

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

Time & Space Complexity

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

Common Pitfalls

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.

# Wrong: if nums[i] > nums[i + 1]
# Correct:
if nums[i] > nums[(i + 1) % N]

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.