{x}
blog image

Check if Array Is Sorted and Rotated

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 <= 100
  • 1 <= nums[i] <= 100

Solution Explanation

The problem asks to determine if an array can be obtained by rotating a sorted array. The core idea is that a sorted array, after rotation, will have at most one point where the elements are out of ascending order. This is because the rotation creates at most one "break" in the sorted sequence.

Approach:

The solution iterates through the array, comparing each element with the next element (wrapping around to the beginning of the array for the last element). A counter (cnt) tracks the number of times a current element is greater than the next. If the counter exceeds 1, it means there are more than one "breaks" in the ascending order, implying the array cannot be a rotated sorted array.

Time Complexity Analysis:

The solution iterates through the array once. Therefore, the time complexity is O(n), where n is the length of the input array.

Space Complexity Analysis:

The solution uses a constant amount of extra space to store the counter variable. Therefore, the space complexity is O(1).

Code Explanation (Python):

class Solution:
    def check(self, nums: List[int]) -> bool:
        return sum(nums[i - 1] > v for i, v in enumerate(nums)) <= 1

This Python code uses a concise one-liner. Let's break it down:

  1. enumerate(nums): This function iterates through the nums array, providing both the index (i) and value (v) of each element.

  2. nums[i - 1] > v: This condition checks if the previous element is greater than the current element. Note that i - 1 will correctly wrap around to the last element when i is 0.

  3. sum(...): This sums up the boolean results (True is 1, False is 0), giving the total count of inversions (where a previous element is greater than the current element).

  4. ... <= 1: This condition checks if the count of inversions is less than or equal to 1. If it is, the array satisfies the condition of being a rotated sorted array.

Code Explanation (Java):

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;
    }
}

The Java code is a more explicit implementation of the same logic:

  1. int cnt = 0;: Initializes a counter for the number of inversions.
  2. for (int i = 0, n = nums.length; i < n; ++i): Iterates through the array. n is pre-calculated for efficiency.
  3. (i + 1) % n: This handles the wrap-around to the beginning of the array for the last element. The modulo operator ensures that when i is n-1, (i+1)%n becomes 0.
  4. if (nums[i] > nums[(i + 1) % n]) { ++cnt; }: Increments the counter if an inversion is found.
  5. return cnt <= 1;: Returns true if there's at most one inversion, otherwise false.

The other languages (C++, Go, TypeScript, Rust, C) follow the same fundamental logic, with minor syntactic variations reflecting the specific features of each language. All of them maintain the same O(n) time and O(1) space complexities.