Watch 10 video solutions for Check if Array Is Sorted and Rotated, a easy level problem involving Array. This walkthrough by if else statement has 31,732 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
1 <= nums.length <= 1001 <= nums[i] <= 100Problem Overview: You are given an integer array. The task is to check whether the array was originally sorted in non-decreasing order and then rotated some number of times. A valid rotated sorted array can have at most one position where the order decreases.
Approach 1: Simulate Rotation (O(n²) time, O(1) space)
The brute force idea is to simulate every possible rotation and check whether the resulting array is sorted. For each rotation index k, construct the rotated order and verify that every element is less than or equal to the next element while iterating through the array. If any rotation produces a sorted sequence, the array satisfies the condition. This approach directly models the definition of rotation but performs a full sorted check for each shift, leading to O(n²) time complexity.
Approach 2: Count Break Points (O(n) time, O(1) space)
A rotated sorted array has a key property: there can be at most one index where nums[i] > nums[i+1]. This position is the rotation pivot. Iterate through the array and count such "break points". Because rotation wraps around, also compare the last and first elements. If the number of breaks is more than one, the array cannot be a rotated sorted array. The algorithm performs a single pass through the array, keeping a counter and checking adjacent values, which makes it efficient and interview-friendly.
The core insight is treating the array as circular. In a perfectly sorted array there are zero decreases, while in a rotated sorted array there is exactly one. This observation eliminates the need for explicitly rotating the array or rebuilding structures.
Recommended for interviews: The break-point counting approach is what interviewers expect. It shows you recognize the structural property of a rotated sorted array and can solve the problem in O(n) time with constant space. Discussing the brute-force rotation check first demonstrates understanding of the problem definition, but implementing the single-pass solution highlights stronger algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate Rotation | O(n²) | O(1) | Useful for understanding the definition of rotation or when demonstrating the brute-force baseline |
| Count Break Points | O(n) | O(1) | Best approach for interviews and production due to linear scan and constant memory |