14. Sorted, Then Rotated?
EasyArray
A carousel holds numbered tags. When it was installed the tags were arranged in non-decreasing order around the ring, but the carousel may since have been turned by some number of positions (possibly zero), so the tag list you read from its starting point may no longer look sorted.
Write a method isRotatedSorted that takes the array nums of tag numbers as read from the current starting point, and returns true if the list could have come from a non-decreasing list by rotating it, and false otherwise.
Example 1
- Input:
- nums = [3,4,5,1,2]
- Output:
- true
- Explanation:
The sorted list 1, 2, 3, 4, 5 rotated by three places gives 3, 4, 5, 1, 2, so the answer is true.
Example 2
- Input:
- nums = [2,1,3,4]
- Output:
- false
- Explanation:
No rotation of any sorted list reads 2, 1, 3, 4, so the answer is false.
Constraints
1 ≤ nums.length ≤ 1000
-1000 ≤ nums[i] ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)