Check if Array is Sorted and Rotated
Check whether an array can be obtained by rotating a nondecreasing array, including a rotation by zero. Duplicate values are allowed.
Work through the cases
3 examplesInput notation
One nonempty line of space-separated integers.Expected result
true or false.Case 1
Input
1 2 2 8
Expected output
true
Case 2
Input
2 1 3 4
Expected output
false
Case 3
Input
3 4 1 2
Expected output
true
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
A nondecreasing array rotated at most once has at most one descent on the circle (nums[i-1]>nums[i] with wrap-around). Count those descents in one pass; the array is valid iff the count is at most 1.
To satisfy the problem's requirement, there can be at most one element in array nums whose value is greater than the next element, i.e., nums[i] \gt nums[i + 1]. If there are more than one such elements, then array nums cannot be obtained by rotation.
Note that the next element after the last element of array nums is the first element of array nums.
The time complexity is O(n), where n is the length of array nums. The space complexity is O(1).
class Solution {
public boolean check(int[] nums) {
int cnt = 0;
for (int i = 0, n = nums.length; i < n; ++i) {
if (nums[i] > nums[(i + 1) % n]) {
++cnt;
}
}
return cnt <= 1;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.