We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if Array Is Sorted and Rotated

Number: 1878

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Meta, Bloomberg, IBM, Adobe, Microsoft, SoundHound

Problem Description

Given an array of numbers, determine if the array was originally sorted in non-decreasing order and then rotated some number of positions (including zero rotations). The array may contain duplicates.

Key Insights

  • A sorted, then rotated array will have at most one position where an element is greater than its immediate next element (taking wrap-around into account).
  • Count the number of "drop" points where nums[i] > nums[(i+1) % n]; if this count is more than one, the array cannot be a rotated sorted array.
  • An array with no drop points or exactly one drop point satisfies the condition.

Space and Time Complexity

Time Complexity: O(n) - we traverse the array once. Space Complexity: O(1) - constant extra space is used.

Solution

We iterate through all elements of the array and compare each element with the next element (using modulo to handle the last element comparing with the first). A counter tracks the number of times an element is greater than its next. If this counter exceeds one, then the array is not sorted and rotated. Otherwise, it is.

Code Solutions

# Function to check if the array is sorted and rotated
def check(nums):
    n = len(nums)
    drop_count = 0  # Count how many times a drop (decrease) occurs
    
    # Iterate over the array and compare with the next element (wrap-around using modulo)
    for i in range(n):
        if nums[i] > nums[(i + 1) % n]:
            drop_count += 1
    # The array is sorted and rotated if there is at most one drop.
    return drop_count <= 1

# Example usage with sample test case
print(check([3, 4, 5, 1, 2]))  # Expected output: True
print(check([2, 1, 3, 4]))     # Expected output: False
← Back to All Questions