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] <= 100In 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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
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 | 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. |
Lecture21: Solving LeetCode/CodeStudio Questions [Arrays] • CodeHelp - by Babbar • 510,635 views views
Watch 9 more video solutions →Practice Check if Array Is Sorted and Rotated with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor