Determine whether an array is non-decreasing after being rotated some number of times.
Problem
Given an integer array, decide whether it can be obtained by taking a non-decreasing sorted array and rotating it any number of positions.
An array is considered valid if, after some rotation, the elements are in sorted non-decreasing order. Duplicate values are allowed.
In other words, check whether the array has at most one place where the order decreases when scanning circularly.
Input Format
- A single integer array
nums. nums[i]are integers and the array length is at least 1.
Output Format
- Return
trueifnumsis sorted and rotated. - Otherwise return
false.
Constraints
- The array may contain duplicate values.
- A valid array has at most one drop in non-decreasing order when considered circularly.
- Aim for time and extra space.
Example 1
Input
nums = [3,4,5,1,2]
Output
true
Explanation
The array is sorted and then rotated. One valid original sorted array is [1,2,3,4,5].
Example 2
Input
nums = [2,1,3,4]
Output
false
Explanation
There are two breaks in order if we view the array circularly, so it cannot come from a single rotation of a sorted array.
Show 1 more example
Example 3
Input
nums = [1,1,1]
Output
true
Explanation
The array is already non-decreasing, and rotating it does not change the order.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.