Check if Array Is Sorted and Rotated — Problem & Solution
Check if Array Is Sorted and Rotated solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Check if Array Is Sorted and Rotated is an easy coding problem on arrays and sorting, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Return true if nums could have been produced by taking an array sorted in non-decreasing order and rotating it by some number of positions (possibly zero); otherwise return false.
Rotating an array a by x positions gives the array b with b[i] = a[(i + x) % a.length]. The array may contain duplicates.
Example 1
Input: nums = [6,8,9,2,4]
Output: true
Explanation: [2,4,6,8,9] rotated by 2 positions.
Example 2
Input: nums = [5,3,4,1]
Output: false
Explanation: The order breaks at 5 → 3 and again at 4 → 1.
Example 3
Input: nums = [7,7,7]
Output: true
Constraints
1 <= nums.length <= 1001 <= nums[i] <= 100
Hints for Check if Array Is Sorted and Rotated
Hint 1
A sorted array has no place where a value is followed by a smaller one.
Hint 2
Rotating it creates at most one such drop — at the seam — if you also compare the last element with the first.
Hint 3
Count indices
iwherenums[i] > nums[(i + 1) % n]; the answer is whether the count is at most 1.
How to solve Check if Array Is Sorted and Rotated
Read the array as a circle. A rotated sorted array, read around the circle, goes down at most once — where the end of the original array meets its start.
Approach
- Count the indices
iwithnums[i] > nums[(i + 1) % n]. - Return
trueif the count is 0 or 1.
Why it works
Rotation does not change the circular order, and a sorted array read circularly has at most one drop (from its last element back to its first). Conversely, if there is at most one circular drop, starting the reading just after it gives a non-decreasing array, which rotates into nums. With zero drops all values are equal, which is sorted too.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Include the wrap-around pair (last, first); without it
[2,1,3,4]would look like one drop and pass. - Duplicates are allowed, so compare with
>, not>=. - A rotation by zero is allowed: an already sorted array is
true.
Reference solution
Python
from typing import List
def check(nums: List[int]) -> bool:
n = len(nums)
drops = sum(1 for i in range(n) if nums[i] > nums[(i + 1) % n])
return drops <= 1Java
public static 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++;
}
return drops <= 1;
}C++
bool check(vector<int>& nums) {
int n = nums.size(), drops = 0;
for (int i = 0; i < n; i++) {
if (nums[i] > nums[(i + 1) % n]) drops++;
}
return drops <= 1;
}JavaScript
var check = function(nums) {
var n = nums.length, drops = 0;
for (var i = 0; i < n; i++) {
if (nums[i] > nums[(i + 1) % n]) drops++;
}
return drops <= 1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms