Check if Array Is Sorted and Rotated
Decide whether an array is a sorted array that has been rotated, in one O(n) pass, by counting the places where a value is larger than the one after it.
Updated Medium read: 8 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Try every rotation | O(n²) | O(1) |
| Count the drops | O(n) | O(1) |
The problem
To rotate an array is to take some items off the front and put them, in the same order, on the end. [2, 4, 6, 8, 9] rotated by three places becomes [8, 9, 2, 4, 6]. Rotating by zero places is allowed and leaves the array as it was.
You are given an array of integers. Return true if it could have been made by sorting some array into ascending order and then rotating it, and false if it could not. Values may repeat, so "ascending" here means each value is greater than or equal to the one before it.
numbers = [8, 9, 2, 4, 6] → true ([2, 4, 6, 8, 9] rotated by 3)
numbers = [2, 4, 6] → true (sorted, rotated by 0)
numbers = [7, 7, 2, 7] → true ([2, 7, 7, 7] rotated by 2)
numbers = [5, 7, 3, 8] → false
numbers = [2, 1, 3, 4] → falseThe last example is the one to keep in mind. It looks almost sorted, with a single pair out of place, and it is still not a rotation of a sorted array.
Approach 1: try every rotation
The most direct reading of the question: if the array is a rotation of something sorted, then reading it from the right starting position, and wrapping round at the end, gives the values in ascending order. There are only n starting positions, so try them all.
Nothing needs to be copied or moved. Reading "from position start, wrapping round" is done with the remainder operator: the item step places after start is at index (start + step) % n.
JavaScript
function isSortedAndRotatedBruteForce(numbers) {
const n = numbers.length;
if (n === 0) return true; // nothing is out of order
for (let start = 0; start < n; start++) {
let inOrder = true;
// Read all n items beginning at start, wrapping round at the end.
for (let step = 1; step < n; step++) {
const previous = numbers[(start + step - 1) % n];
const current = numbers[(start + step) % n];
if (previous > current) {
inOrder = false;
break;
}
}
if (inOrder) return true;
}
return false;
}Python
def is_sorted_and_rotated_brute_force(numbers):
n = len(numbers)
if n == 0:
return True # nothing is out of order
for start in range(n):
in_order = True
# Read all n items beginning at start, wrapping round at the end.
for step in range(1, n):
previous = numbers[(start + step - 1) % n]
current = numbers[(start + step) % n]
if previous > current:
in_order = False
break
if in_order:
return True
return FalseTime O(n²): up to n starting positions, and up to n - 1 comparisons for each. Space O(1).
For [8, 9, 2, 4, 6] the starts 0 and 1 fail quickly (the reading hits 9 followed by 2), and start 2 succeeds: 2, 4, 6, 8, 9.
It is correct and easy to trust, which makes it a good reference to test a faster version against. But it repeats work. Every starting position compares the same neighbouring pairs; it just begins somewhere else.
What a rotated sorted array looks like
Call a place where a value is larger than the one after it a drop. A sorted array has no drops. Now join its two ends into a ring, so the last item is followed by the first:
sorted, as a ring: 2 → 4 → 6 → 8 → 9 ─┐
↑ │
└──────────────────┘ 9 back to 2: one dropThe ring has exactly one drop, where the largest value meets the smallest. (If every value is the same there are none.) Rotating the array does not change the ring at all. It only changes which item you call the first. So:
An array is a sorted array that has been rotated exactly when its ring has at most one drop.
The reverse direction holds too. If the ring has one drop, start reading just after it: you go all the way round without meeting another drop, so what you read is sorted. If the ring has no drops, every value is equal and the array is already sorted.
Approach 2: count the drops
Compare every item with the one after it, treating the first item as the one after the last. Count the drops. Stop early if a second one appears.
JavaScript
function isSortedAndRotated(numbers) {
const n = numbers.length;
let drops = 0;
for (let i = 0; i < n; i++) {
const next = numbers[(i + 1) % n]; // after the last item comes the first
if (numbers[i] > next) {
drops++;
if (drops > 1) return false;
}
}
return true;
}Python
def is_sorted_and_rotated(numbers):
n = len(numbers)
drops = 0
for i in range(n):
following = numbers[(i + 1) % n] # after the last item comes the first
if numbers[i] > following:
drops += 1
if drops > 1:
return False
return TrueThe comparison is a strict >. Two equal neighbours are in ascending order as far as this problem is concerned, so they are not a drop.
Walkthrough
numbers = [8, 9, 2, 4, 6]:
| i | numbers[i] | Next item | Drop? | Drops so far |
|---|---|---|---|---|
| 0 | 8 | 9 | No | 0 |
| 1 | 9 | 2 | Yes | 1 |
| 2 | 2 | 4 | No | 1 |
| 3 | 4 | 6 | No | 1 |
| 4 | 6 | 8 (wraps to index 0) | No | 1 |
One drop: return true.
numbers = [2, 1, 3, 4], the almost-sorted example:
| i | numbers[i] | Next item | Drop? | Drops so far |
|---|---|---|---|---|
| 0 | 2 | 1 | Yes | 1 |
| 1 | 1 | 3 | No | 1 |
| 2 | 3 | 4 | No | 1 |
| 3 | 4 | 2 (wraps to index 0) | Yes | 2 |
Two drops: return false. Without the wrap-around comparison in the last row, the count would have stopped at one and the answer would have been wrong. That comparison is what checks that the two sorted runs fit together: everything after the drop must be no larger than the first item.
Time O(n): one pass with one comparison per item. Space O(1).
Comparing the approaches
| Try every rotation | Count the drops | |
|---|---|---|
| Time | O(n²) | O(n) |
| Space | O(1) | O(1) |
| Comparisons for 1,000 items, worst case | About 1,000,000 | 1,000 |
| Handles duplicates | Yes | Yes |
| Idea needed | None beyond the definition | The ring has at most one drop |
O(n) is the best possible here. An answer of true is only safe once every neighbouring pair has been looked at, because a single pair anywhere can spoil it. There is no way to skip half the array as a binary search does.
The drop is the central idea of the whole rotated sorted arrays pattern. Once you know an array has just one, you can find it without looking at every item: see Find Minimum in Rotated Sorted Array.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
console.log(isSortedAndRotated([8, 9, 2, 4, 6])); // true
console.log(isSortedAndRotated([2, 4, 6])); // true
console.log(isSortedAndRotated([7, 7, 2, 7])); // true
console.log(isSortedAndRotated([5, 7, 3, 8])); // false
console.log(isSortedAndRotated([2, 1, 3, 4])); // falsePython
print(is_sorted_and_rotated([8, 9, 2, 4, 6])) # True
print(is_sorted_and_rotated([2, 4, 6])) # True
print(is_sorted_and_rotated([7, 7, 2, 7])) # True
print(is_sorted_and_rotated([5, 7, 3, 8])) # False
print(is_sorted_and_rotated([2, 1, 3, 4])) # FalseThe comment after each line is the result you should see.
Common mistakes
- Leaving out the wrap-around comparison. Counting drops only between neighbours inside the array accepts
[2, 1, 3, 4]. The last item must also be compared with the first. - Counting equal neighbours as a drop. Using
>=rejects[7, 7, 2, 7]and even[4, 4, 4]. Only a strictly larger value followed by a smaller one counts. - Requiring exactly one drop. An array of identical values, or of a single item, has none and is still sorted. The test is "at most one".
- Reading past the end.
numbers[i + 1]at the last index isundefinedin JavaScript and an error in Python. The% nkeeps the index inside the array. - Building each rotation as a new array. Slicing and joining for every starting position works, but it adds O(n) memory and copying for no benefit; the remainder operator reads the same items in place.
Original problem: LeetCode 1752: Check if Array Is Sorted and Rotated