#1752
Check if Array Is Sorted and Rotated
Easy Count drops
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether the array could be a non-decreasing array that was rotated some number of positions (duplicates allowed).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: could this be a sorted array that was rotated?
Why this works: walk around the array in a circle and count the "drops" (a value bigger than the next). A rotated sorted array has at most one drop.
Example: [3, 4, 5, 1, 2]
3→4 ok, 4→5 ok, 5→1 drop, 1→2 ok, 2→3 (wrap) ok1 drop → true
✦Hints open one at a time
In a sorted array there is no place where a value is larger than the next one.
In a rotated sorted array there is at most one such "drop" — if you also compare the last element with the first.
↗Approach
Count indexes i where nums[i] > nums[(i + 1) % n]. The array is a rotated sorted array exactly when that count is at most 1.
</>Solution (Java)
class Solution {
public boolean check(int[] nums) {
int n = nums.length, drops = 0;
for (int i = 0; i < n; i++) {
if (nums[i] > nums[(i + 1) % n]) drops++; // includes last -> first
}
return drops <= 1;
}
}!Common mistake
Forgetting the wrap-around comparison between the last and first element.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Arrays
