Check if Array Is Sorted and Rotated
EasyPrompt
Given an array nums, return true if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return false.
There may be duplicates in the original array.
Note: An array A rotated by x positions results in an array B of the same length such that B[i] == A[(i+x) % A.length] for every valid index i.
Example 1:
Input: nums = [3,4,5,1,2]
Output: true
Explanation: [1,2,3,4,5] is the original sorted array.
You can rotate the array by x = 3 positions to begin on the element of value 3: [3,4,5,1,2].Example 2:
Input: nums = [2,1,3,4]
Output: false
Explanation: There is no sorted array once rotated that can make nums.Example 3:
Input: nums = [1,2,3]
Output: true
Explanation: [1,2,3] is the original sorted array.
You can rotate the array by x = 0 positions (i.e. no rotation) to make nums.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the problem's definition. It first creates a sorted version of the input array. Then, it generates every possible rotation of this sorted array and compares each one with the original input array. If any of the rotated versions match the input array, the function returns true; otherwise, it returns false after checking all possibilities.
Algorithm
- Create a copy of the input array
numsand sort it. Let's call thissortedNums. - Iterate through all possible rotation offsets, from
0ton-1, wherenis the length of the array. - For each rotation offset
x, check if the original arraynumsis equal to thesortedNumsarray rotated byx. - To check for equality, iterate from
i = 0ton-1and comparenums[i]withsortedNums[(i + x) % n]. - If a match is found for any rotation
x, returntrueimmediately. - If the loops complete without finding any matching rotation, return
false.
Walkthrough
The brute-force method is the most straightforward way to solve the problem. The core idea is to verify if the given array nums can be produced by rotating a sorted version of itself.
- Sort a Copy: First, we create a new array,
sortedNums, which is a sorted version of the inputnums. This gives us the 'original sorted array' mentioned in the problem description. - Generate and Compare Rotations: We then systematically generate all
npossible rotations ofsortedNums. A rotation byxpositions means the element at indexiin the sorted array moves to index(i + x) % n. For each of thesenrotations, we compare it element-by-element with the originalnumsarray. - Return Result: If we find any rotation of
sortedNumsthat is identical tonums, we've confirmed thatnumsis a sorted and rotated array, so we returntrue. If we exhaust allnpossible rotations without finding a match, it meansnumscannot be formed this way, and we returnfalse.
import java.util.Arrays; class Solution { public boolean check(int[] nums) { int n = nums.length; int[] sortedNums = new int[n]; System.arraycopy(nums, 0, sortedNums, 0, n); Arrays.sort(sortedNums); // Try all n possible rotation offsets for (int x = 0; x < n; x++) { boolean match = true; // Check if this rotation matches the original array for (int i = 0; i < n; i++) { if (nums[i] != sortedNums[(i + x) % n]) { match = false; break; } } if (match) { return true; } } return false; }}Complexity
Time
O(N^2). Sorting the array takes O(N log N). The outer loop runs N times (for each rotation), and the inner loop for comparison also runs N times. This results in a complexity of O(N log N + N*N), which simplifies to O(N^2).
Space
O(N), where N is the number of elements in the array. This space is used to store the `sortedNums` array.
Trade-offs
Pros
Easy to understand and implement as it directly follows the problem statement.
Guaranteed to be correct.
Cons
Highly inefficient with a time complexity of O(N^2), which is slow for larger arrays.
Requires O(N) extra space to store the sorted copy of the array.
This approach is based on the observation that if an array is sorted and rotated, the minimum element of the array acts as the pivot point where the rotation occurred. By finding this minimum element, we can identify the potential starting point of the original sorted sequence. We then verify if the array is sorted in non-decreasing order starting from this pivot and wrapping around.
Algorithm
- Find the index of the minimum element in the array. Let this be
minIndex. This requires a single pass through the array. - If there are multiple minimum elements, any of their indices will work as the potential start of the sorted sequence.
- Once
minIndexis found, treat the array as if it starts from this index and wraps around. - Perform a second pass to verify if this 'un-rotated' sequence is sorted. Iterate from
i = 0ton-2. - In each step of the second pass, compare
nums[(minIndex + i) % n]withnums[(minIndex + i + 1) % n]. - If you find any pair where
nums[(minIndex + i) % n] > nums[(minIndex + i + 1) % n], the array is not correctly sorted and rotated, so returnfalse. - If the second pass completes without finding any such pair, the array is valid. Return
true.
Walkthrough
A more optimized approach involves locating the pivot of the rotation. In a non-decreasingly sorted and rotated array, the smallest element is the pivot. For example, in [3,4,5,1,2], the minimum element 1 is where the original sorted sequence [1,2,3,4,5] begins.
- Find the Minimum: The first step is to iterate through the array to find the index of the minimum element. Let's call this
minIndex. - Verify Sorted Order: Once we have the
minIndex, we can conceptually 'un-rotate' the array. We then perform a second pass, starting fromminIndex, to check if the elements are in non-decreasing order. This check involves comparing each element with its successor, wrapping around the end of the array to the beginning. The comparison looks likenums[current_index] <= nums[next_index], where indices are calculated using the modulo operator to handle the wrap-around. - Return Result: If all elements from the pivot point onwards are in sorted order, the function returns
true. If at any point the order is broken, we can immediately returnfalse.
class Solution { public boolean check(int[] nums) { int n = nums.length; if (n <= 1) { return true; } // 1. Find the index of the minimum element int minIndex = 0; for (int i = 1; i < n; i++) { if (nums[i] < nums[minIndex]) { minIndex = i; } } // 2. Check if the array is sorted starting from minIndex for (int i = 0; i < n - 1; i++) { int currentIndex = (minIndex + i) % n; int nextIndex = (minIndex + i + 1) % n; if (nums[currentIndex] > nums[nextIndex]) { return false; } } return true; }}Complexity
Time
O(N). The first pass to find the minimum element takes O(N) time. The second pass to verify the sorted order also takes O(N) time. The total time complexity is O(N + N) = O(N).
Space
O(1), as it only uses a few variables to store indices and does not require any additional data structures proportional to the input size.
Trade-offs
Pros
Efficient O(N) time complexity.
Optimal O(1) space complexity as it modifies nothing in place.
Cons
Requires two passes over the array, which is slightly less efficient than a single-pass solution.
This is the most efficient approach. It leverages a key insight: a non-decreasingly sorted array that has been rotated will have at most one point where an element is greater than the element that follows it. This includes the 'wrap-around' case where the last element is compared to the first. By making a single pass through the array and counting these 'breaks' or 'inversions', we can solve the problem.
Algorithm
- Initialize a counter variable,
breaks, to zero. - Iterate through the array from
i = 0ton-1. - In each iteration, compare the current element
nums[i]with the next elementnums[(i + 1) % n]. The modulo operator% nis crucial here as it handles the wrap-around comparison between the last and the first element. - If
nums[i] > nums[(i + 1) % n], it signifies a 'break' in the non-decreasing order. Increment thebreakscounter. - After the loop finishes, check the value of
breaks. - If
breaksis 0 (array is fully sorted with no breaks) or 1 (array is rotated once), the condition is satisfied. Returntrue. - If
breaksis greater than 1, it means there are multiple points of disorder, so the array could not have been formed from a single sorted sequence. Returnfalse.
Walkthrough
The optimal solution is elegant and relies on a simple observation. When a sorted array is rotated, it creates at most one 'discontinuity' or 'break point' where nums[i] > nums[i+1].
- A perfectly sorted array like
[1, 2, 3, 4]has zero such breaks. If we consider the wrap-around from last to first element (4 > 1), there is one break. - A rotated array like
[3, 4, 1, 2]has one break (4 > 1). - An unsorted array like
[2, 1, 3, 4]has two breaks (2 > 1and4 > 2when wrapping around).
Therefore, an array is a sorted and rotated version of another if and only if the number of these breaks is less than or equal to one. We can simply iterate through the array once, count the number of breaks, and return the result.
The check nums[i] > nums[(i + 1) % n] cleverly handles both internal breaks and the wrap-around break between the last and first elements in a single loop.
class Solution { public boolean check(int[] nums) { int n = nums.length; int breaks = 0; for (int i = 0; i < n; i++) { // Compare current element with the next, wrapping around using modulo if (nums[i] > nums[(i + 1) % n]) { breaks++; } } // If there is 0 or 1 break, the array is sorted and rotated. return breaks <= 1; }}Complexity
Time
O(N). The algorithm iterates through the array exactly once, performing a constant number of operations at each step.
Space
O(1). It only requires a single integer variable (`breaks`) for counting, resulting in constant extra space.
Trade-offs
Pros
Most efficient solution with O(N) time complexity in a single pass.
Optimal O(1) space complexity.
The code is very concise and elegant.
Cons
The logic, while concise, might be slightly less intuitive to grasp initially compared to more direct methods.
Solutions
Solution
class Solution {public boolean check(int[] nums) { int cnt = 0; for (int i = 0, n = nums.length; i < n; ++i) { if (nums[i] > nums[(i + 1) % n]) { ++cnt; } } return cnt <= 1; }}class Solution {public: bool check(vector<int> &nums) { int cnt = 0; for (int i = 0, n = nums.size(); i < n; ++i) { cnt += nums[i] > (nums[(i + 1) % n]); } return cnt <= 1; }};class Solution: def check(self, nums: List[int]) -> bool: return sum( nums[i - 1] > v for i, v in enumerate(nums)) <= 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.