3011. Find if Array Can Be Sorted - Detailed Explanation
Problem Statement
Given an integer array nums, determine if it can be obtained by taking a sorted (non-decreasing) array and rotating it some number of times (possibly zero times). In other words, check if nums was originally sorted in non-decreasing order, then rotated (shifted cyclically) by some positions. If yes, return true; otherwise, return false. The array may contain duplicates, which are allowed in the sorted order.
-
Rotation Definition: Rotating an array by x positions means taking the first x elements and moving them to the end (in order). For example, rotating
[1,2,3,4,5]byx=2positions results in[3,4,5,1,2]. Formally, for an array A, rotation by x yields an array B such thatB[i] = A[(i+x) % A.length]. -
Constraints: Typical constraints for this problem are small to moderate size (e.g.
1 <= nums.length <= 100and1 <= nums[i] <= 100). This means a brute-force solution is feasible for the given limits, but understanding the optimal solution is valuable for larger scenarios.
Examples:
-
Example 1:
- Input:
nums = [3,4,5,1,2] - Output:
true - Explanation:
[1,2,3,4,5]is the original sorted array. Rotating it byx = 3positions (bringing the last 3 elements to the front) yields[3,4,5,1,2], which matches the input.
- Input:
-
Example 2:
- Input:
nums = [2,1,3,4] - Output:
false - Explanation: No sorted array can be rotated to form
[2,1,3,4]. If we try to split it into two sorted parts, they overlap improperly. This array breaks the sorted-then-rotated pattern at more than one point, so it cannot come from a single sorted rotation.
- Input:
-
Example 3:
- Input:
nums = [1,2,3] - Output:
true - Explanation: The array is already sorted (non-decreasing) and requires no rotation. (Rotating by
0positions is allowed, so an already sorted array trivially satisfies the condition.)
- Input:
Hints
-
Identify the Pattern: If an array is sorted and then rotated, it will have at most one "break" point where the ordering drops. That is, it will look like two sorted subarrays – one from the rotation point to the end, and one from the start to the rotation point – with the last element of the array less than or equal to the first element (for a proper rotation).
-
Brute Force Thought: Consider simulating all possible rotations of the array. If any rotation yields a fully sorted array, then the answer is true. While this is not efficient for very large arrays, it’s a direct way to verify the condition given the small constraints.
-
Efficient Insight: You don’t actually need to try all rotations. Try scanning through the array to find if and where it breaks the sorted order. Count how many times
nums[i] > nums[i+1]occurs (treating the array as circular). If this count is more than 1, the array fails the condition. If the count is 0 or 1 (at most one drop), it passes – but if it's exactly 1, also ensure the last element is not greater than the first element (to confirm the wrap-around is valid). -
Use of Modulus for Wrap-around: When checking adjacent pairs, remember to compare the last element with the first element as well (circular comparison). A common trick is to use indices modulo
nto handle this in one loop.
Now, let's explore multiple approaches to solve this problem.
Approach 1: Brute Force (Checking All Possible Rotations)
Detailed Explanation:
The brute force approach explicitly simulates every possible rotation of the array and checks if any rotation is sorted in non-decreasing order. An array of length n can be rotated n ways (including a rotation by 0 which leaves it unchanged). For each rotation, we can form the rotated array and then verify if it is sorted. If we find a sorted rotation, we return true; if none of the rotations produce a sorted array, we return false.
Steps for this approach:
-
Iterate over all rotation offsets
kfrom0ton-1. A rotation bykmeans the element originally at indexkbecomes the first element of the rotated array. -
Construct the rotated array for each
k. This can be done by taking the subarray fromkto end, and then from start tok-1. For example, fork=3on[3,4,5,1,2], the rotated array is[1,2] + [3,4,5] = [1,2,3,4,5]. -
Check if the rotated array is sorted (each element <= next element).
-
If any rotated version is sorted, return true; if none are sorted, return false.
Because we explicitly generate each rotation and check it, the time complexity is higher (quadratic in the worst case), but it’s straightforward and works within given constraints.
Python Code Implementation (Brute Force):
Java Code Implementation (Brute Force):
Discussion: The brute force approach is easy to understand and implement. We directly simulate rotations and use a helper to check sorting. Given the constraint n <= 100, the maximum of 100 rotations each checking up to 100 elements (total ~10,000 checks) is very fast. However, for a larger array (if n were in the thousands or more), this approach would be inefficient (O(n²) time). We can do better by observing the array’s properties without full simulation.
Approach 2: Optimal Approach (Single Pass – Finding the Breaking Point)
Detailed Explanation:
A more efficient solution uses the observation that a sorted-then-rotated array will have at most one place where an element is greater than the next element (this is the "break" or rotation point). We can detect this in a single pass:
-
Traverse the array and count how many times an adjacent pair is out of order (i.e.,
nums[i] > nums[i+1]). Let’s call these occurrences "drops". -
Because the array is conceptually circular (rotated), also consider the pair formed by the last and first element. If
nums[last] > nums[first], that indicates a drop when wrapping around. -
If the total count of drops is 0, the array is already sorted (no rotation needed, return true). If the count is exactly 1, that means the array has one rotation point and is otherwise sorted – this is a valid rotated sorted array (return true). If the count is more than 1, the array breaks sorted order in multiple places, so return false.
-
One extra consideration: If there is exactly one drop, ensure that this drop indeed represents a rotation point. In practice, this means checking that the last element of the array is not greater than the first element (otherwise, the array would have two increasing sequences that don't connect properly). The algorithm inherently handles this by counting the wrap-around comparison as a drop if needed.
This approach only requires a single loop through the array (constant extra space), making it optimal with O(n) time.
Python Code Implementation (Optimal)
Java Code Implementation (Optimal):
Discussion: This optimal approach uses a single pass through the array to count the number of disorder points. It leverages the problem’s special structure (a sorted array can be "broken" at only one point by rotation). By including the comparison between the last and first elements, we seamlessly handle the circular nature of rotation. The result is a very efficient check: for example, in one line it can be implemented by summing such conditions and checking if the sum is <= 1. This solution runs in linear time and constant space, making it suitable for large inputs as well.
Complexity Analysis
-
Brute Force Approach: Time complexity is O(n²) in the worst case. We try up to
nrotations and each rotation check takes O(n) time to verify sorted order, so roughly n * n operations. Space complexity is O(n) if we allocate a new array for each rotation (which in total might use more than n, but each rotation uses O(n) space). We could optimize space by rotating in-place or using pointers to avoid full copies, but the time cost remains quadratic. Given the constraints (n up to 100), this approach is acceptable, but it would scale poorly for large n. -
Optimal Single-Pass Approach: Time complexity is O(n) since we make a single pass through the array (just a few comparisons per element). Space complexity is O(1) extra space, using only a few counters/variables. This approach is optimal for this problem. Even if n were very large, this method would be efficient.
Both approaches are efficient for the given constraint bounds, but the optimal approach is clearly better for larger input sizes.
Common Mistakes
-
Missing the Wrap-around Check: A very frequent mistake is to scan the array for a drop (
nums[i] > nums[i+1]) but forget to compare the last element with the first element. Remember that because of rotation, the array is conceptually circular. Failing to checknums[n-1]vsnums[0]can lead to incorrect results (e.g., saying an already sorted array with last > first is invalid, or missing the rotation point at the boundary). -
Allowing More than One Break: Some might incorrectly assume any drop invalidates the array. In reality, one drop is allowed (that’s the rotation point). If you return false upon the first drop without checking the rest, you might incorrectly label a valid rotated array as false. Conversely, simply checking two sorted segments separately without the additional condition can lead to accepting invalid arrays. Ensure you count the breaks across the entire circular array.
-
Off-by-One Errors: When implementing the rotation or the checks, off-by-one indexing issues can occur. For example, iterating the wrong range when checking adjacent pairs, or miscomputing rotation slices. Using modulus arithmetic or clearly separating the last-first comparison helps avoid these mistakes.
-
Not Handling Trivial Cases: Edge cases like single-element arrays, all equal elements, or already sorted arrays should be handled. For instance, a single element or all duplicates should trivially return true (as they are sorted and any rotation is the same array). Make sure your logic doesn’t falsely flag these cases (e.g., the wrap-around check should be carefully written so that in an already sorted array with
nums[-1] > nums[0]it still returns true because that single break is allowed). -
Misinterpreting "rotation" direction: Rotation direction doesn't actually matter here (rotating left or right by some positions yields a set of possible arrays). The problem definition uses one convention (as per the modulo formula), but practically any cyclic shift is accounted for by some
x. Just ensure you are consistent with how you simulate or check the rotation.
Edge Cases
Consider the following edge scenarios to ensure your solution handles them correctly:
-
Single Element: e.g.
[10]. This should return true, since a one-element array is trivially sorted and any rotation is itself. -
Two Elements: e.g.
[1,2](already sorted, true) and[2,1](rotated sorted, true). With two elements, if they are not sorted, they must be a rotation of the sorted order. Ensure your logic catches that[2,1]is a valid rotation of[1,2]. -
Already Sorted Array: e.g.
[1,2,3,4]. This should return true (rotation by 0). Check that your method doesn’t wrongly require a rotation to happen. An already sorted array will have no internal drop; our check should count 0 drops as valid. -
Already Sorted but Last < First: This scenario only happens if the array is not strictly increasing. For instance,
[1,1,1](all equal) is already sorted and also appears rotated (last == first). Or consider[2,2,3,4,4](non-decreasing). It’s sorted, and because duplicates exist, the last element (4) is not greater than the first (2), which might trigger a wrap check incorrectly if not careful. Our logic should still return true (at most one drop, which would actually be 0 here). Make sure the wrap comparison uses>(strictly greater) rather than>=so that equal values do not count as a break. -
All Elements Equal: e.g.
[7,7,7]. This should return true. There are 0 drops (no decrease anywhere, and wrap-around check finds last (7) > first (7) is false since 7 is not greater than 7). Any rotation doesn’t change the array. -
Multiple Possible Rotation Points (Duplicates): e.g.
[1,2,2,3,1]. This array has a drop at the end (3 -> 1 wrap-around) and is otherwise sorted. It should return true. Duplicates can sometimes confuse algorithms if not careful (ensuring non-decreasing order rather than strictly increasing). Our approach counts a break only when a number is greater than the next number, not greater-or-equal, so it handles duplicates correctly. -
Invalid Cases: e.g.
[3,1,2,4,5]– here the sequence breaks at3->1and also the last element5is greater than the first3(wrap-around break), so it’s not a single rotation of a sorted array (should return false). Another invalid example:[1,3,2,2]– breaks at3->2and also at wrap2->1, false. -
Large Rotations: If the array was rotated
n-1times (almost the entire length), e.g. original[1,2,3,4]rotated 3 times gives[2,3,4,1]. The logic should still only find one drop (4->1). This is covered by our method but is a good sanity check.
Alternative Variations
-
Strictly Increasing Sequence: A variation is if the original array must be strictly increasing (no duplicates allowed in sorted order). The solution approach is similar, except you would count a "drop" when
nums[i] >= nums[i+1]in that case (since an equal would violate strictly increasing). The rotation check logic remains analogous. -
Rotation in Opposite Direction: The problem doesn’t specify left or right rotation explicitly (the formula given implies a left rotation by x). However, any right rotation by y is equivalent to a left rotation by
n-y. So the condition doesn’t change with rotation direction – any cyclic shift works. A variation could explicitly ask if the array is a rotation in a particular direction (but since rotation is cyclic, the check is the same set of arrays). -
Almost Sorted (One Swap or One Reversal): In a different problem, one might ask if the array can be sorted by a single swap of two elements, or by reversing one contiguous subarray. Those are different from rotation, but also involve minimal changes to sorted order. For example, one-swap to sort would involve at most one pair out of order; one-subarray reversal to sort can be checked by finding the first and last indices where the array differs from a sorted copy. These problems use different strategies (greedy or two-pointer checks) but are conceptually about “nearly sorted” arrays.
-
Rotated Sorted Array Search: In other scenarios, you might not just check the rotated sorted array, but search within it (classic binary search modifications). Problems like finding an element in a rotated sorted array or finding the rotation index use the sorted-rotated structure in different ways. While not the same task, they rely on the idea of one discontinuity in order.
Related Problems for Further Practice
To deepen your understanding, you can practice these related problems:
-
LeetCode 33: Search in Rotated Sorted Array – Medium. Given a sorted array that has been rotated, find a target value’s index. Involves binary search with rotation logic.
-
LeetCode 153: Find Minimum in Rotated Sorted Array – Medium. Find the smallest element in a rotated sorted array (which is effectively the rotation pivot). This builds on similar concepts of a single break point.
-
LeetCode 154: Find Minimum in Rotated Sorted Array II – Hard. Similar to above but the array may contain duplicates, making the logic a bit trickier.
-
LeetCode 189: Rotate Array – Medium. Rotate an array by k steps. This is the inverse operation (actively rotating an array), which helps understand rotations more concretely.
-
LeetCode 665: Non-decreasing Array – Medium. Check if you can make an array non-decreasing (sorted) by modifying at most one element. This is about detecting if at most one change can fix the order, conceptually akin to allowing one "break" in sorted order as well.
-
Check if One String is a Rotation of Another (Classic interview problem) – Not a LeetCode problem, but a well-known variation where you check if one string can be rotated to form another. It can be solved by doubling one string and searching for the other as a substring, highlighting a different application of the rotation concept.
GET YOUR FREE
Coding Questions Catalog
