LeetCode Solution: 1752. Check if Array Is Sorted and Rotated

#leetcode #dsa #programming #tutorial

🔄 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
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
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.
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.

*   `[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 <vector> // Don't forget to include necessary headers!
#include <iostream> // For potential testing, though not strictly part of the solution

class Solution {
public:
    bool check(std::vector<int>& 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.
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).

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