1752. Check if Array Is Sorted and Rotated

Array

TIME

O(n)

SPACE

O(1)

Intuition

In a non-decreasing sorted array, every adjacent pair satisfies nums[i] <= nums[i + 1].

After rotation, there can be one drop where the end of the larger suffix wraps to the start of the smaller prefix. If we also compare the last element with the first element, a valid sorted-and-rotated array has at most one drop.

Approach

Initialize drops = 0.
For every index i, compare nums[i] with nums[(i + 1) % n].
If nums[i] > nums[(i + 1) % n], increment drops.
Return true if drops <= 1, otherwise return false.

Complexity

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

Edge Cases

Already sorted array -> zero or one circular drop, so return true
Single-element array -> return true
Duplicates -> allowed because the sorted order is non-decreasing
More than one drop -> cannot be a rotation of a sorted array

Code

from typing import List


class Solution:
    def check(self, nums: List[int]) -> bool:
        """
        1752. Check if Array Is Sorted and Rotated
        Time: O(n)
        Space: O(1)
        """
        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

/**
 * 1752. Check if Array Is Sorted and Rotated
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public boolean check(int[] nums) {
        int drops = 0;
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            if (nums[i] > nums[(i + 1) % n]) {
                drops++;

                if (drops > 1) {
                    return false;
                }
            }
        }

        return true;
    }
}