Problem Description
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.
Key Insights
- The array can be considered sorted if there is at most one point where the order is broken (i.e., a larger number appears before a smaller number).
- A rotated sorted array will have at most one such "pivot" point.
- Handle duplicates carefully, as they can affect the identification of sorted sequences.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
To determine if the array is sorted and rotated, we can traverse the array while counting the number of times the order is broken. This involves checking if the current element is greater than the next element. If we find more than one such point, the array is not sorted and rotated. We also need to account for duplicates that may create ambiguity in determining the sorted nature.