# LeetCode Solution: 1752. Check if Array Is Sorted and Rotated > Source: > Published: 2026-05-23 18:17:13+00:00 # πŸ”„ LeetCode 1752: Can You Un-Rotate This Array? (A Beginner's Guide) Hey there, fellow coders! πŸ‘‹ Vansh2710 here, ready to demystify another exciting LeetCode challenge. Today, we're tackling problem 1752: "Check if Array Is Sorted and Rotated." Sounds a bit like a puzzle, right? Don't worry, we'll break it down piece by piece and uncover a super elegant solution! This problem is a fantastic way to sharpen your array manipulation and logical thinking skills. It might seem tricky at first, but with a simple trick, it becomes incredibly straightforward. Let's dive in! ### What's the Problem All About? 🧐 Imagine you have a perfectly sorted list of numbers, like `[1, 2, 3, 4, 5]` . Now, imagine you *rotate* it. This means you take some elements from the beginning and move them to the end, keeping their relative order. For example, if you rotate `[1, 2, 3, 4, 5]` by 2 positions: `[1, 2, 3, 4, 5]` - Take `1, 2` and move them to the end:`[3, 4, 5, 1, 2]` The problem asks: **Given an array nums, can we tell if it could have been originally sorted (non-decreasingly) and then rotated some number of times (even zero rotations)?** **Key things to remember:** - **Non-decreasing order:**`[1, 2, 2, 3]` is sorted.`[3, 2, 1]` is not. - **Rotation:** Can be any number of positions, including 0 (no rotation). - **Duplicates are allowed:** This is an important detail!`[3, 4, 5, 5, 1, 2]` could be`[1, 2, 3, 4, 5, 5]` rotated. **Let's look at examples:** - `nums = [3, 4, 5, 1, 2]` - Is `[1, 2, 3, 4, 5]` sorted? Yes. - Can `[1, 2, 3, 4, 5]` be rotated to get`[3, 4, 5, 1, 2]` ? Yes, rotate by 2 positions. - **Output:**`true` - Is - `nums = [2, 1, 3, 4]` - If sorted, it would be `[1, 2, 3, 4]` . - Can `[1, 2, 3, 4]` be rotated to`[2, 1, 3, 4]` ? No. The`2, 1` part breaks the sorted order that a single rotation would maintain. - **Output:**`false` - If sorted, it would be - `nums = [1, 2, 3]` - Is it sorted? Yes. - Can it be rotated to get `[1, 2, 3]` ? Yes, 0 rotations. - **Output:**`true` ### The "Aha!" Moment - Our Intuition ✨ Think about a truly sorted array like `[1, 2, 3, 4, 5]` . If you go from left to right, `nums[i-1]` is always less than or equal to `nums[i]` . There are no "drops" or "descents" in value. Now, consider a *rotated* sorted array: `[3, 4, 5, 1, 2]` . If you scan this, you'll see: - `3 <= 4` (OK) - `4 <= 5` (OK) - `5 > 1` (AHA! A**descent**!) - `1 <= 2` (OK) Notice something? There's only *one place* where the non-decreasing order is broken: `5` followed by `1` . This "break" is exactly where the rotation happened! The elements `[1, 2]` were moved from the beginning to the end, creating this single drop in value. What if there are *two* descents? For example, `[2, 1, 3, 4]` . - `2 > 1` (Descent 1) - `1 <= 3` (OK) - `3 <= 4` (OK) Here, we have one descent. What about the wrap-around?`4 > 2` ? No. Actually, if the original array was`[1,2,3,4]` , and we rotated it, we would*never*get`[2,1,3,4]` . A single rotation implies that*all*elements after the rotation point are smaller than*all*elements before it. The only "break" can be at the rotation point. So, the core intuition is: **A sorted and rotated array will have at most ONE "descent" (where nums[i-1] > nums[i]) when you iterate through it.** **Wait, what about the wrap-around?** Consider `[4, 5, 1, 2, 3]` . `4 <= 5` (OK) `5 > 1` (Descent!) `1 <= 2` (OK) `2 <= 3` (OK) Here, we have one descent. But also, `nums[n-1]` (which is `3` ) is less than `nums[0]` (which is `4` ). This comparison also forms part of the "break" in sorted order, conceptually wrapping around the array. Our descent counter needs to account for this. **Revised Intuition:** Count the number of times `nums[i-1] > nums[i]` . This count should be at most 1, *including* the wrap-around comparison between the last and first elements. ### Step-by-Step Approach πŸšΆβ™‚οΈ Let's formalize our intuition into a clear algorithm: **Initialize a counter:** We'll need a variable, let's call it`descentCount` , and set it to`0` . This counter will track how many times we find`nums[i-1] > nums[i]` .- **Iterate through the array:** Loop from the second element (`i = 1` ) up to the end of the array (`nums.size() - 1` ).- In each iteration, compare the current element ( `nums[i]` ) with the previous one (`nums[i-1]` ). - If `nums[i-1] > nums[i]` , it means we've found a "descent" or a break in the non-decreasing order. Increment`descentCount` . - In each iteration, compare the current element ( - **Check the wrap-around case:** After the loop finishes, we need to consider the connection between the*last*element and the*first*element. In a rotated sorted array, if there was a rotation, the last element might be greater than the first element (e.g., in`[3, 4, 5, 1, 2]` ,`nums[4]` (which is`2` ) is less than`nums[0]` (which is`3` ). This doesn't add a descent. However, in`[1,2,3]` (0 rotations),`nums[2]` (3) is greater than`nums[0]` (1). Let's re-evaluate: The descent is where the sequence*decreases*.- `[3, 4, 5, 1, 2]` ->`5 > 1` (1 descent)- `nums[n-1]` (2) is*not*greater than`nums[0]` (3). - - `[1, 2, 3]` -> No descents.- `nums[n-1]` (3) is*not*greater than`nums[0]` (1). - - `[2, 1, 3, 4]` ->`2 > 1` (1 descent)- `nums[n-1]` (4) is*not*greater than`nums[0]` (2). - My logic for the wrap-around check in the solution code is `if (nums[n-1] > nums[0])` . Let's trace it with examples:- `[3,4,5,1,2]` (n=5)- Loop: `(5 > 1)` ->`descentCount = 1` - Wrap-around: `nums[4]` (2)`>` `nums[0]` (3) is`false` . - Total `descentCount = 1` . Return`true` . Correct. - Loop: - ``` php * `[2,1,3,4]` (n=4) * Loop: `(2 > 1)` -> `descentCount = 1` * Wrap-around: `nums[3]` (4) `>` `nums[0]` (2) is `true`. -> `descentCount = 2`. * Total `descentCount = 2`. Return `false`. Correct. (Because original `[1,2,3,4]` cannot be rotated to `[2,1,3,4]`. It has two "breaks" if you consider it circular: `2->1` and `4->2` (conceptual circular link)). * `[1,2,3]` (n=3) * Loop: No descents. `descentCount = 0`. * Wrap-around: `nums[2]` (3) `>` `nums[0]` (1) is `true`. -> `descentCount = 1`. * Total `descentCount = 1`. Return `true`. Correct. (A sorted array is considered a 0-rotated sorted array). This wrap-around check for `nums[n-1] > nums[0]` cleverly handles the case where the "rotation point" effectively exists between the last and first element *if the array was originally sorted*. If `[1,2,3]` is seen as `1,2,3,1` (circular), then `3 > 1` is a descent. This means a perfectly sorted array will register 1 descent with this method. ``` - **Final Check:** After iterating through the array and checking the wrap-around, if`descentCount` is less than or equal to`1` , it means the array*could have been*sorted and rotated. Return`true` . Otherwise, if`descentCount` is greater than`1` , it means there are too many "breaks" in the sorted order for it to be a single rotation of a sorted array. Return`false` . ### Show Me the Code! πŸ’» Here's the C++ implementation of this logic: ``` #include // Don't forget to include necessary headers! #include // For potential testing, though not strictly part of the solution class Solution { public: bool check(std::vector& nums) { int count = 0; // Initialize descent counter int n = nums.size(); // Get the size of the array // Iterate from the second element to compare with the previous for (int i = 1; i < n; i++) { // If the previous element is greater than the current, it's a descent if (nums[i-1] > nums[i]) { count++; } } // Handle the wrap-around case: compare the last element with the first // If nums[n-1] is greater than nums[0], it means a "descent" occurs // conceptually between the end and the beginning of the array. // E.g., for [1,2,3], nums[2](3) > nums[0](1) is true. // For [3,4,5,1,2], nums[4](2) > nums[0](3) is false. if (nums[n-1] > nums[0]) { count++; } // A sorted and rotated array can have at most one "descent" (break). // This includes the wrap-around check, meaning a perfectly sorted array // will result in count = 1 due to the wrap-around check. return count <= 1; } }; ``` ### Complexity Analysis β±οΈπŸš€ Let `N` be the number of elements in the `nums` array. - **Time Complexity: O(N)**- We iterate through the array once in the `for` loop, which takes`O(N)` time. - All other operations (initialization, `size()` call, final comparison) take constant time,`O(1)` . - Therefore, the total time complexity is dominated by the loop, making it `O(N)` . This is highly efficient as we only need to pass through the array once. - We iterate through the array once in the - **Space Complexity: O(1)**- We only use a few extra variables ( `count` ,`n` ,`i` ) to store our state, regardless of the input array size. - No auxiliary data structures (like new arrays or hash maps) are used that scale with the input size. - Thus, the space complexity is constant, `O(1)` . - We only use a few extra variables ( ### Key Takeaways ✨ - **Spotting the "Breaks":** The most crucial insight is that a sorted and rotated array will have at most one point where the non-decreasing order is violated. - **The Wrap-Around is Tricky:** Don't forget the connection between the last element and the first! This is where many solutions go wrong. Our approach correctly includes this as another potential "descent." - **Simple is Often Best:** This problem could tempt you into complex sorting or array manipulation, but a single pass and a counter prove to be the most elegant and efficient solution. This approach is clean, efficient, and demonstrates a good understanding of array properties! Keep practicing, and you'll master these patterns in no time. Happy coding! **Author Account:** Vansh2710 **Time Published:** 2026-05-23 23:46:54