1752. Check if Array Is Sorted and Rotated
Asked at Google
Difficulty
Easy
Time
O(n)
Space
O(1)
Pattern
Array
Companies
1
Problem
You are given an array of integers nums. Return true if this array could have been made by taking a non-decreasing sorted array and rotating it some number of positions (rotating by 0 is allowed). Otherwise return false.
A rotation by x positions moves the first x elements to the back, so the element that was at index x becomes the new first element. The array may contain duplicate values, and duplicates are fine — they do not break the sorted order.
A useful way to think about it: a sorted array never goes down. Rotating it cuts the array at one point and moves the front part to the back, so the result can go down at most once (at that cut). So just count how many times the array steps down.
A rotation creates one downward step
Constraints
- ●
1 <= nums.length <= 100 - ●
1 <= nums[i] <= 100
Examples
nums = [3,4,5,1,2]truenums = [2,1,3,4]falsenums = [1,2,3]trueAsked At
1 companies| 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 >.
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).
Count the drops, including the wrap
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
O(n) timedef 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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.