Is Check if Array Is Sorted and Rotated easy or hard?

The problem is classified as Easy on LeetCode. The main challenge is recognizing that a rotated sorted array can only have one decreasing pair. Once that insight is clear, the implementation becomes a straightforward O(n) scan.

Check if Array Is Sorted and Rotated Python/Java solution

The typical implementation iterates through the array and increments a counter whenever nums[i] > nums[i+1]. After the loop, compare nums[n-1] with nums[0] for the circular condition. This logic works identically in Python, Java, C++, JavaScript, and other languages.

How to solve Check if Array Is Sorted and Rotated in O(n)?

Traverse the array and count how many times the order decreases, meaning nums[i] > nums[i+1]. Also check the circular pair nums[n-1] and nums[0]. If the number of decreases is greater than one, the array is not a rotated sorted array. Otherwise it satisfies the condition.

What is the best approach for Check if Array Is Sorted and Rotated?

The most efficient approach is counting break points in the array. Iterate once and count positions where nums[i] > nums[i+1], including the circular comparison between the last and first element. A valid rotated sorted array has at most one such drop. This solution runs in O(n) time and O(1) space.

Is Check if Array Is Sorted and Rotated asked at Google/Amazon/Meta?

Variants of rotated array checks appear in interviews at companies like Amazon, Google, and Meta, usually as warm-up array problems. They test whether you can identify structural properties in arrays and reduce the problem to a single linear pass.

What data structure is used in Check if Array Is Sorted and Rotated?

The problem primarily uses a simple array traversal. No additional data structures such as hash maps or stacks are required. The optimal solution relies on sequential comparison of neighboring elements in the array.

What is the time complexity of Check if Array Is Sorted and Rotated?

The optimal solution runs in O(n) time because it scans the array once and compares adjacent elements. Space complexity is O(1) since only a counter variable is used. A brute-force rotation simulation would take O(n²) time.

Description Hints 1 Solution Video 10:57

1752. Check if Array Is Sorted and Rotated

Easy57.3% acceptance10 companies

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 A[i] == B[(i+x) % A.length], where % is the modulo operation.

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 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: