Check if Array Is Sorted and Rotated
Easy· circular array
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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)
