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:

1
2
3
4

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:

1
2
3

Input: nums = [2,1,3,4]
Output: false
Explanation: There is no sorted array once rotated that can make nums.

Example 3:

1
2
3
4

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:

  1. 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.
  2. 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].

  1. Rotation 0 (no rotation): [3, 4, 5, 1, 2] (not sorted)
  2. Rotation 1: [4, 5, 1, 2, 3] (not sorted)
  3. Rotation 2: [5, 1, 2, 3, 4] (not sorted)
  4. Rotation 3: [1, 2, 3, 4, 5] (sorted, return true)

Pseudocode

Here is the pseudocode:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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 takes O(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).
  • 🧺 Space complexity: O(n) for storing the rotated arrays.

Method 2 - Count the transitions

Here is the approach:

  1. Identify the number of places where the array transitions from a higher to a lower value.
  2. This transition can occur at most once in a valid rotated sorted array.
  3. 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 at 5 -> 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 at 5 -> 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 element 5 compared to the first element 1 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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].
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 return true.

Here is the approach:

  1. 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.
  2. Find Sorted Window: Use a sliding window of size n to check if any of the subarrays of size n in the doubled array are sorted in non-decreasing order.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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)
  • 🧺 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:

  1. Initial Setup:

    • Calculate the length of the array n.
    • Initialize window_size to track the current size of the sorted window.

  2. Sliding Window:

    • Iterate through indices from 0 to 2 * n - 1 to simulate a sliding window over the array.
    • For each i, use the modulo operator to access elements in a circular manner.

  3. Check Sorted Window:

    • Compare nums[i % n] with nums[(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 reaches n, return True.

  4. No Sorted Window Found:

    • If no sorted window is found after checking all possible windows, return False.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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.