Check if Array Is Sorted and Rotated
Easy· circular array
Problem
Decide whether an array could have been produced by taking a non-decreasing array and rotating it by some number of positions (possibly zero). Duplicates are allowed.
Examples
Input: nums = [4,5,1,2,3]
Output: true
Rotating [1,2,3,4,5] by three positions gives this array.
Input: nums = [2,1,3,4]
Output: false
The drop from 2 to 1 and the wrap-around from 4 to 2 are two breaks, which no rotation can produce.
Constraints
- • 1 <= nums.length <= 100
- • 1 <= nums[i] <= 100
Hints & approach
Hint 1
In a sorted array, how many times does a value exceed its right neighbour?
Hint 2
After rotation there can be at most one such drop, if you also compare the last element with the first.
Approachtry the hints first
Count positions i where nums[i] > nums[(i + 1) % n], treating the array as circular. A sorted array rotated by any amount has at most one such "drop" (the seam where the rotation happened). So the answer is true exactly when the count is 0 or 1.
Time O(n) · Space O(1)