Check if Array Is Sorted and Rotated
Asked at Google
Problem
Determine whether an array could have been produced by rotating a non-decreasing sorted array at some pivot. A sorted array has at most one descending step, so the whole check reduces to counting adjacent drops including the wrap - a Google speed-round favorite that runs in one pass.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → |
How to Think About It
Baseline: try every rotation and, for each, compare against a sorted copy of the array. With n rotations and O(n) comparisons each, the check is O(n²) - simple but far too slow.
Key insight: a non-decreasing sorted array has exactly zero drops, where a drop is a pair of adjacent positions with left > right. Rotating moves the largest element to the front, which introduces exactly one drop at the wrap point.
The check becomes: count the drops, including the circular pair between the last and first elements via nums[(i + 1) % n]. A valid sorted-and-rotated array has at most one such drop; zero drops means it is sorted as-is.
Why at most one: two or more drops means the sequence changed direction more than once, which a single rotation of a sorted list can never produce. Equal elements are harmless because drops require a strict >.
Visual walkthrough for nums = [3, 4, 5, 1, 2]:
- pairs: (3,4) ok, (4,5) ok, (5,1) drop, (1,2) ok, (2,3) ok.
- exactly 1 drop -> True (it is [1,2,3,4,5] rotated left by 2).
- compare [1, 3, 2, 4]: (1,3) ok, (3,2) drop, (2,4) ok, (4,1) drop -> 2 drops -> False.
Edge cases: a single element has 0 drops and is always True; all equal elements give 0 drops and are True; the original sorted array gives 0 drops and is valid since a zero-position rotation counts.
Optimal Approach
Iterate once over the array counting adjacent drops, where a drop is a pair (i, i+1) with nums[i] > nums[i+1], and also check the wrap pair nums[n-1] > nums[0] using modulo arithmetic. The array is a valid sorted-then-rotated array exactly when the drop count is at most one: zero drops means it is already sorted, one drop means it was cut at that descent and rotated.
Walkthrough for nums = [2, 1, 3, 4]:
- Adjacent pairs: (2,1) is a drop, (1,3) ok, (3,4) ok, wrap (4,2) is a drop.
- Total drops = 2 > 1, so false. Indeed [2,1,3,4] is no rotation of a sorted array.
- Compare [1, 2, 3, 4]: 0 drops, true. [3, 4, 1, 2]: only (4,1) and (2,3) - the wrap pair is not a drop, so exactly 1 drop, true.
Time: O(n) space: O(1).
What Trips People Up in Real Interviews
Using >= instead of > for the drop comparison. Equal adjacent values are not a drop, so >= wrongly rejects valid duplicate-heavy arrays like [1, 1, 1, 2, 2] (0 drops, valid).
Forgetting the circular pair between the last and first elements. The rotation lives at the wrap, so a linear-only scan misses that drop and mislabels arrays rotated past the fold as invalid.
Over-verifying: hunting for the max element or a specific pivot index. The drop-count predicate is complete on its own - locating the pivot adds complexity and invites off-by-one mistakes for no benefit.
Mishandling the modulo. (i + 1) % n wraps the final index to 0; using a bare i + 1 on the last element indexes out of bounds or compares against garbage.
Reporting the inversion count instead of the adjacent-drop count. An array can hold many inversions yet still be a valid rotation (for example with duplicates) - the answer depends only on adjacent pairs.
Solution Code
def check(nums):
n = len(nums)
drops = 0
for i in range(n):
if nums[i] > nums[(i + 1) % n]:
drops += 1
return drops <= 1Frequently Asked Questions
What is the Check if Array Is Sorted and Rotated problem?
Determine whether an array could have been produced by rotating a non-decreasing sorted array at some pivot. A sorted array has at most one descending step, so the whole check reduces to counting adjacent drops including the wrap - a Google speed-round favorite that runs in one pass.
How do you solve Check if Array Is Sorted and Rotated?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Check if Array Is Sorted and Rotated?
Check if Array Is Sorted and Rotated is asked at Google. It is a easy difficulty problem.
What are common mistakes on Check if Array Is Sorted and Rotated?
- Using `>=` instead of `>` for the drop comparison. Equal adjacent values are not a drop, so `>=` wrongly rejects valid duplicate-heavy arrays like `[1, 1, 1, 2, 2]` (0 drops, valid).
- Forgetting the circular pair between the last and first elements. The rotation lives at the wrap, so a linear-only scan misses that drop and mislabels arrays rotated past the fold as invalid.
- Over-verifying: hunting for the max element or a specific pivot index. The drop-count predicate is complete on its own - locating the pivot adds complexity and invites off-by-one mistakes for no benefit.
- Mishandling the modulo. `(i + 1) % n` wraps the final index to 0; using a bare `i + 1` on the last element indexes out of bounds or compares against garbage.
- Reporting the inversion count instead of the adjacent-drop count. An array can hold many inversions yet still be a valid rotation (for example with duplicates) - the answer depends only on adjacent pairs.