Check if Array Is Sorted and Rotated - Solution & Explanation
Problem Statement
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] <= 100
Approach Overview
Problem 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 1: Count Break Points
In a rotated sorted array, there should be exactly one point where a number is greater than its subsequent number, marking the 'rotation break'. We iterate over the array to count how many such breaks exist.
The function iterates over the array and checks for any descending order transition, counting how many such transitions exist. If more than one exists, it returns false. Otherwise, it returns true.
Complexity
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1) as it uses a constant amount of additional space.
Approach 2: Simulate Rotation
This approach involves simulating the rotation of a sorted version of the input array and checking if it matches the original array. This is done by sorting the array, and then checking each possible rotation for a match.
This solution first sorts the array and then attempts to match every rotation position of the sorted array against the input array. It utilizes a separate memory allocation to perform the simulation.
Complexity
Time Complexity: O(n^2) due to sorting and subsequent rotation checks.
Space Complexity: O(n) as it requires additional space for the sorted array.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Count Break Points | Time Complexity: O(n), where n is the number of elements in the array. |
| Simulate Rotation | Time Complexity: O(n^2) due to sorting and subsequent rotation checks. |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Check if Array Is Sorted and Rotated - Leetcode 1752 - Python • NeetCodeIO • 33,528 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Check if Array Is Sorted and Rotated easy or hard?
Check if Array Is Sorted and Rotated Python/Java solution
How to solve Check if Array Is Sorted and Rotated in O(n)?
What is the best approach for Check if Array Is Sorted and Rotated?
Is Check if Array Is Sorted and Rotated asked at Google/Amazon/Meta?
What data structure is used in Check if Array Is Sorted and Rotated?
What is the time complexity of Check if Array Is Sorted and Rotated?
Ready to solve this problem?
Practice Check if Array Is Sorted and Rotated with our built-in code editor and test cases.
Practice on FleetCode