Problem Description

You're given an array nums and need to determine if it could be a rotated version of a sorted array.

The problem asks you to check if the array was originally sorted in non-decreasing order (elements can be equal or increasing) and then possibly rotated some number of positions. A rotation means taking some elements from the beginning and moving them to the end while maintaining their order.

For example:

• [1, 2, 3, 4, 5] rotated by 2 positions becomes [3, 4, 5, 1, 2]
• [2, 2, 3, 1, 1] could be a rotation of [1, 1, 2, 2, 3]

The array may contain duplicate values, which means equal consecutive elements are allowed.

The solution works by counting how many times a value is smaller than its previous element (a "break point"). In a valid rotated sorted array, there can be at most one such break point:

• If there are 0 break points, the array is already sorted
• If there is 1 break point, the array is a rotated sorted array
• If there are 2 or more break points, the array cannot be a rotated sorted array

The code sum(nums[i - 1] > v for i, v in enumerate(nums)) <= 1 counts these break points by comparing each element with its previous one (including wrapping from the last element to the first) and returns True if there's at most one break point.

Intuition

To understand if an array is a rotated sorted array, let's think about what happens when we rotate a sorted array.

When we take a sorted array like [1, 2, 3, 4, 5] and rotate it, we're essentially cutting it at some point and swapping the two parts. For instance, rotating by 2 gives us [3, 4, 5, 1, 2].

The key observation is: in the resulting array, there's exactly one place where the order "breaks" - where a larger number is followed by a smaller number. In our example, that's between 5 and 1. This is the rotation point.

If we scan through the array and count how many times we see this pattern (where nums[i-1] > nums[i]), we can determine:

• 0 breaks: The array is already sorted and hasn't been rotated
• 1 break: The array is a valid rotated sorted array
• More than 1 break: The array cannot be a rotated sorted array because rotating a sorted array can only create one discontinuity

There's one subtle detail: when comparing elements, we also need to check the wrap-around from the last element to the first element. If nums[n-1] > nums[0], that counts as a break too. This handles cases where the rotation point is at the beginning or end.

The beauty of this approach is that we don't need to actually find where the rotation happened or reconstruct the original array - we just need to verify that the pattern matches what a rotated sorted array would look like.

Solution Approach

The solution uses a single-line implementation that elegantly counts the number of "breaks" in the array:

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

Let's break down how this works:

1. Enumeration and Comparison

• enumerate(nums) iterates through the array, giving us both the index i and value v at each position
• For each element, we compare it with its previous element using nums[i - 1] > v

2. Handling the Wrap-Around

• When i = 0, the expression nums[i - 1] becomes nums[-1], which in Python refers to the last element
• This automatically handles the comparison between the last and first elements, checking if there's a break at the rotation boundary

3. Counting Breaks

• The generator expression nums[i - 1] > v for i, v in enumerate(nums) produces True (1) when there's a break and False (0) otherwise
• sum() counts the total number of True values, giving us the total number of breaks

4. Final Check

• The condition <= 1 returns True if there's at most one break, confirming the array is either:
  • Already sorted (0 breaks)
  • A valid rotated sorted array (1 break)

Example Walkthrough:

• For [3, 4, 5, 1, 2]: comparisons are (2,3), (3,4), (4,5), (5,1), (1,2). Only (5,1) is a break, so sum = 1, returns True
• For [2, 1, 3, 4]: comparisons are (4,2), (2,1), (1,3), (3,4). Both (4,2) and (2,1) are breaks, so sum = 2, returns False

The algorithm runs in O(n) time with O(1) extra space, making it optimal for this problem.

Example Walkthrough

Let's walk through the solution with the array [4, 5, 6, 7, 1, 2, 3].

This array is actually a rotated version of [1, 2, 3, 4, 5, 6, 7], rotated 4 positions to the right.

Step 1: Set up the comparisons We'll check each element against its previous element, including the wrap-around from last to first:

Step 2: Count the breaks Going through our comparisons:

• Positions 0, 1, 2, 3, 5, 6: No breaks (contribute 0 to sum)
• Position 4: One break where 7 > 1 (contributes 1 to sum)

Total sum = 1

Step 3: Apply the check Since sum(breaks) = 1 ≤ 1, the function returns True.

This confirms that [4, 5, 6, 7, 1, 2, 3] is indeed a valid rotated sorted array. The single break at position 4 represents the rotation point where the array was "cut" and the parts were swapped.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array nums. The code iterates through the array once using enumerate(), and for each element, it performs a constant-time comparison (nums[i - 1] > v). The sum() function processes all n comparisons, resulting in linear time complexity.

Space Complexity: O(1). The generator expression (nums[i - 1] > v for i, v in enumerate(nums)) doesn't create an intermediate list but yields values one at a time to the sum() function. Only a constant amount of extra space is used for the loop variables (i, v) and the accumulator in sum(), regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Rotation Point Check

Pitfall: Assuming that checking only adjacent elements (without the wrap-around) is sufficient. Some might write:

def check(self, nums: List[int]) -> bool:
    break_count = 0
    for i in range(1, len(nums)):  # Starting from 1, missing wrap-around
        if nums[i-1] > nums[i]:
            break_count += 1
    return break_count <= 1

This fails for cases like [2, 1] where the only break is between the last and first element.

Solution: Always include the wrap-around comparison between the last and first element. The original solution handles this elegantly with nums[i-1] when i=0, which automatically becomes nums[-1].

2. Edge Case with Single Element

Pitfall: Not considering arrays with only one element. While the given solution handles this correctly, manual implementations might fail:

def check(self, nums: List[int]) -> bool:
    if len(nums) == 0:  # Unnecessary check that might miss single element case
        return True
    # ... rest of logic

Solution: The original solution naturally handles single-element arrays since the comparison nums[-1] > nums[0] compares the element with itself, which is always False.

3. Strict vs Non-Strict Inequality

Pitfall: Using >= instead of > in the comparison:

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

This would incorrectly count equal consecutive elements as breaks. For example, [1, 1, 1] would have 3 "breaks" and return False.

Solution: Use strict inequality (>) to only count actual decreases, not equal values. The array [1, 1, 2, 2, 3] should be valid since equal consecutive elements are allowed in a sorted array.

4. Off-by-One Error in Manual Implementation

Pitfall: When manually implementing the circular check, forgetting to compare the last element with the first:

def check(self, nums: List[int]) -> bool:
    break_count = 0
    # Check all adjacent pairs
    for i in range(1, len(nums)):
        if nums[i-1] > nums[i]:
            break_count += 1
    # Forgot to check nums[-1] > nums[0]!
    return break_count <= 1

Solution: Either use the elegant enumeration approach that automatically handles wrap-around, or explicitly add the boundary check:

def check(self, nums: List[int]) -> bool:
    break_count = 0
    n = len(nums)
    for i in range(n):
        if nums[(i-1) % n] > nums[i]:  # Using modulo for clarity
            break_count += 1
    return break_count <= 1