Problem
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 A[i] == B[(i+x) % A.length]
, where %
is the modulo operation.
Examples
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 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 <= 100
1 <= nums[i] <= 100
Solution
Video explanation
Here is the video explaining below methods in detail. Please check it out:
Method 1 - Naive
Now the naive approach can be:
- For each possible position in the array, we rotate the array to the left - in a way undoing the rotation to the right given in the original.
- Validate if the array is sorted in any of the rotations. If it is, then the array was rotated and sorted; otherwise, it was not.
Consider the array nums = [3, 4, 5, 1, 2]
.
- Rotation 0 (no rotation):
[3, 4, 5, 1, 2]
(not sorted) - Rotation 1:
[4, 5, 1, 2, 3]
(not sorted) - Rotation 2:
[5, 1, 2, 3, 4]
(not sorted) - Rotation 3:
[1, 2, 3, 4, 5]
(sorted, returntrue
)
Pseudocode
Here is the pseudocode:
function check(nums):
n = length(nums)
for x from 0 to n-1:
rotated = rotate(nums, x)
if isArraySorted(rotated):
return true
return false
function rotate(arr, x):
return arr[x:] + arr[:x]
function isArraySorted(arr):
for i from 1 to length(arr):
if arr[i-1] > arr[i]:
return false
return true
Code
Java
public class Solution {
public boolean check(int[] nums) {
int n = nums.length;
// Try all rotations
for (int x = 0; x < n; x++) {
if (isSorted(rotate(nums, x))) {
return true;
}
}
return false;
}
// Function to rotate the array by x positions
private int[] rotate(int[] nums, int x) {
int n = nums.length;
int[] rotated = new int[n];
for (int i = 0; i < n; i++) {
rotated[i] = nums[(x + i) % n];
}
return rotated;
}
// Function to check if the array is sorted in non-decreasing order
private boolean isSorted(int[] arr) {
for (int i = 1; i < arr.length; i++) {
if (arr[i - 1] > arr[i]) {
return false;
}
}
return true;
}
}
Python
class Solution:
def check(self, nums: List[int]) -> bool:
n = len(nums)
# Function to check if the array is sorted in non-decreasing order
def is_sorted(arr: List[int]) -> bool:
for i in range(1, len(arr)):
if arr[i-1] > arr[i]:
return False
return True
# Try all rotations
for x in range(n):
rotated = nums[x:] + nums[:x] # Rotate array by x positions
if is_sorted(rotated):
return True
return False
Complexity
- ⏰ Time complexity:
O(n^2)
. Generating rotations takesO(n^2)
because we generate a new array for each rotation.- Checking if an array is sorted takes
O(n)
. - So the overall complexity is
O(n^2)
.
- Checking if an array is sorted takes
- 🧺 Space complexity:
O(n)
for storing the rotated arrays.
Method 2 - Count the transitions
Here is the approach:
- Identify the number of places where the array transitions from a higher to a lower value.
- This transition can occur at most once in a valid rotated sorted array.
- If the transition happens more than once, then the array isn’t a valid rotated sorted array.
Lets take some examples.
- Consider
nums = [3, 4, 5, 1, 2]
. The array experiences a transition at5 -> 1
, which is one transition. Then,2 -> 3
is considered a continuation due to the circular nature, making it valid. - For
nums = [1, 3, 5, 1, 2]
, there is one transition at5 -> 1
. However,1
is not connected properly, indicating the array is not a valid sorted rotation. - For
nums = [1, 2, 3, 4, 5]
, there are no transitions from start to end. However, the last element5
compared to the first element1
forms one transition, which is valid. - For
nums = [1, 1, 1, 1]
, there are no transitions, indicating a valid extensively sorted array with no rotations required.
Code
Java
class Solution {
public boolean check(int[] nums) {
int n = nums.length;
int trans = 0;
for (int i = 0; i < n; i++) {
if (nums[i] > nums[(i+1) % n]) {
trans++;
}
if (trans > 1) {
return false;
}
}
return true;
}
}
Python
class Solution:
def check(self, nums: List[int]) -> bool:
n = len(nums)
trans: int = 0
for i in range(n):
if nums[i] > nums[(i + 1) % n]:
trans += 1
if trans > 1:
return False
return True
Complexity
- ⏰ Time complexity:
O(n)
, where n is the length of the array, as we need to check each element. - 🧺 Space complexity:
O(1)
, as we are using a constant amount of extra space.
Method 3 - Doubling the array + Sliding Window
Consider nums = [3, 4, 5, 1, 2]
:
- The doubled array is
[3, 4, 5, 1, 2, 3, 4, 5, 1, 2]
.
[3, 4, 5, 1, 2, 3, 4, 5, 1, 2]
^ ^
- Use a sliding window of size
n = 5
:- Subarray
[3, 4, 5, 1, 2]
is not sorted. - Subarray
[4, 5, 1, 2, 3]
is not sorted. - Subarray
[5, 1, 2, 3, 4]
is not sorted. - Subarray
[1, 2, 3, 4, 5]
is sorted, so we returntrue
.
- Subarray
Here is the approach:
- Double the Array: Create a new array by concatenating the original array with itself. This helps in visualizing all possible rotations in a linear fashion.
- Find Sorted Window: Use a sliding window of size
n
to check if any of the subarrays of sizen
in the doubled array are sorted in non-decreasing order.
Code
Java
class Solution {
public boolean check(int[] nums) {
int n = nums.length;
// Step 1: Double the array
int[] doubledNums = new int[2 * n];
System.arraycopy(nums, 0, doubledNums, 0, n);
System.arraycopy(nums, 0, doubledNums, n, n);
// Step 2: Use sliding window to check for sorted subarray of size n
int windowSize = 1;
// We start the loop from 1 to ensure we have a previous element to compare to
for (int i = 1; i < 2 * n; i++) {
if (doubledNums[i - 1] <= doubledNums[i]) {
windowSize++;
} else {
windowSize = 1;
}
// If we find a sorted subarray of length n, return true
if (windowSize == n) {
return true;
}
}
// For n == 1, we need an explicit check before starting the loop
return n == 1;
}
}
Python
class Solution:
def check(self, nums: List[int]) -> bool:
n = len(nums)
# For a single element array, it's trivially sorted and rotated
if n == 1:
return True
window_size = 1
# Use sliding window with modulo operator to handle circular array
for i in range(1, 2 * n):
if nums[(i - 1) % n] <= nums[i % n]:
window_size += 1
else:
window_size = 1
if window_size == n:
return True
return False
Complexity
- ⏰ Time complexity:
O(n)
- Doubling the array takes
O(n)
time - Then, we check for subarrays of size n, and we may have to restart again in case we find an element which is not in sorted order, but we will start from the new point…and will go through each element only once in this doubled array, so it is
O(2n)
=O(n)
- Doubling the array takes
- 🧺 Space complexity:
O(n)
for storing the doubled array (O(2n)
=O(n)
)
Method 4 - Doubling the array using modulo operator + Sliding window
Here is the approach:
Initial Setup:
- Calculate the length of the array
n
. - Initialize
window_size
to track the current size of the sorted window.
- Calculate the length of the array
Sliding Window:
- Iterate through indices from
0
to2 * n - 1
to simulate a sliding window over the array. - For each
i
, use the modulo operator to access elements in a circular manner.
- Iterate through indices from
Check Sorted Window:
- Compare
nums[i % n]
withnums[(i + 1) % n]
. - If the elements are in non-decreasing order, increase
window_size
. - If they are not, reset
window_size
to 1. - If
window_size
reachesn
, returnTrue
.
- Compare
No Sorted Window Found:
- If no sorted window is found after checking all possible windows, return
False
.
- If no sorted window is found after checking all possible windows, return
Code
Java
class Solution {
public boolean check(int[] nums) {
int n = nums.length;
// For a single element array, it's trivially sorted and rotated
if (n == 1) {
return true;
}
int windowSize = 1;
// Use sliding window with modulo operator to handle circular array
for (int i = 1; i < 2 * n; i++) {
if (nums[(i - 1) % n] <= nums[i % n]) {
windowSize++;
} else {
windowSize = 1; // Reset window size
}
if (windowSize == n) {
return true;
}
}
return false;
}
}
Python
class Solution:
def check(self, nums: List[int]) -> bool:
n = len(nums)
# For a single element array, it's trivially sorted and rotated
if n == 1:
return True
window_size = 1
# Use sliding window with modulo operator to handle circular array
for i in range(1, 2 * n):
if nums[(i - 1) % n] <= nums[i % n]:
window_size += 1
else:
window_size = 1
if window_size == n:
return True
return False
Complexity
- ⏰ Time complexity:
O(n)
- 🧺 Space complexity:
O(1)
as now we are using modulo operator instead of doubling the array.