#1752

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Check if Array Is Sorted and Rotated

Determine if a given integer array is sorted in non-decreasing order and then rotated, handling duplicates correctly.

Problem Statement

Given an integer array nums, determine whether it was originally sorted in non-decreasing order and then rotated any number of positions, including zero. Return true if it meets these conditions, otherwise return false. Duplicates may exist in the array.

Rotation is defined such that for an array A rotated by x positions, the resulting array B satisfies B[i] == A[(i+x) % A.length] for every valid index i. Your task is to verify whether the current arrangement of nums can result from such a rotation of a sorted array.

Examples

Example 1

Input: nums = [3,4,5,1,2]

Output: true

[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

There is no sorted array once rotated that can make nums.

Example 3

Input: nums = [1,2,3]

Output: true

[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 Approach

Count Descending Pairs

Traverse the array and count the number of times a current element is greater than the next element, considering wrap-around. If more than one descending pair exists, the array cannot be a rotated sorted array.

Handle Edge Cases

Check arrays with all identical elements or arrays with zero rotations separately. This prevents false negatives when duplicates or no rotation are present.

Single Pass Verification

Perform a single pass through the array comparing each element to the next modulo the array length. Return true if descending pairs are zero or one, which confirms a valid rotation.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because we traverse the array once. Space complexity is O(1) since we only track a counter for descending pairs and use no additional data structures.

What Interviewers Usually Probe

Watch for multiple descending points indicating invalid rotation.
Check wrap-around comparisons at the array boundaries carefully.
Handle duplicates correctly to avoid miscounting descending pairs.

Common Pitfalls or Variants

Common pitfalls

Failing to count the descending pair between the last and first element.
Assuming zero rotation must be ignored, which can cause false negatives.
Overlooking duplicate elements that do not break the sorted rotation property.

Follow-up variants

Determine if an array is strictly increasing and rotated without duplicates.
Check if an array can be sorted in non-increasing order and rotated.
Find the minimum number of rotations needed to make an array sorted.

FAQ

What is a simple method to check if an array is sorted and rotated?

Count descending pairs in a single pass and ensure there is at most one, including wrap-around from the last to the first element.

Does this method work with duplicate elements?

Yes, duplicates do not increase descending pairs unless they violate non-decreasing order.

What if the array is already sorted and not rotated?

The algorithm treats zero rotations as valid, so a fully sorted array returns true.

Can this approach handle arrays of length 1 or 2?

Yes, arrays with one or two elements are always considered sorted and possibly rotated.

Is there a more efficient approach than O(n) for this problem?

No, any method must at least examine each element to check the descending pair count, so O(n) is optimal.

terminal

Solution

Solution 1

#### Python3

1

2

3

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

Continue Practicing

#1751 maximum number of events that can be attended ii #1749 maximum absolute sum of any subarray #1755 closest subsequence sum