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

#leetcode #dsa #programming #tutorial

Mastering Rotated Arrays: A Beginner-Friendly Look at LeetCode 1752

Hey fellow coders! 👋 Today, we're diving into a super common and insightful LeetCode problem that's perfect for strengthening your array manipulation skills: 1752. Check if Array Is Sorted and Rotated.

It sounds a bit tricky, but with a simple trick, we can unmask the mystery of these rotated arrays! Let's conquer it together.

🚀 Problem Explanation

Imagine you have a perfectly sorted array of numbers in non-decreasing order (meaning numbers either go up or stay the same). For example: [1, 2, 3, 4, 5].

Now, imagine we take this array and "rotate" it. This means we move some elements from the beginning to the end, maintaining their relative order.

For instance, if we rotate [1, 2, 3, 4, 5] by 2 positions, 1 and 2 move to the end:
[3, 4, 5, 1, 2]

The problem asks us to determine: Given an array nums, can it be formed by taking some originally sorted, non-decreasing array and rotating it?

Important notes:

Non-decreasing: [1, 1, 2, 3] is sorted non-decreasingly. Duplicates are allowed!
Rotation: You can rotate by any number of positions, including zero (which means no rotation at all, just a plain sorted array).

Let's look at the examples:

Example 1: nums = [3,4,5,1,2]

This can be [1,2,3,4,5] rotated by 2 positions.
Output: true

Example 2: nums = [2,1,3,4]

Can you find an originally sorted array that could become this after rotation? No.
Output: false

Example 3: nums = [1,2,3]

This is already sorted. It's like rotating by 0 positions.
Output: true

Constraints are small (nums.length up to 100), so efficiency won't be a huge bottleneck, allowing us to focus on the logic!

🤔 Intuition: The "One Break" Rule

This is where the "aha!" moment happens. Think about what happens when you rotate a sorted array.

A perfectly sorted array (no rotation):
[1, 2, 3, 4, 5]
If you compare adjacent elements, nums[i-1] will always be less than or equal to nums[i]. There are no "breaks" where the order goes down.
A sorted array rotated once:
[3, 4, 5, 1, 2]
Notice how most elements maintain their non-decreasing order: 3 <= 4, 4 <= 5, 1 <= 2.
But there's exactly one spot where this breaks: 5 > 1. This is the point where the array "wraps around" from its largest element back to its smallest.
An array that's NOT sorted and rotated:
[2, 1, 3, 4]
Here, 2 > 1 is a break. And then 3 <= 4 is fine. What if we consider the "wrap-around" too? If it was [1,2,3,4] rotated, it would have one break. But [2,1,3,4] has 2>1. If we trace the original array [1,2,3,4] rotated one time, it would be [4,1,2,3], which also has only one break (4>1).
The key insight is: A valid sorted and rotated array (including 0 rotations) will have at most one point where nums[i-1] > nums[i]. This "break" signifies the point of rotation. If we find more than one such break, it means the array wasn't originally sorted.

Let's test this "one break" rule:

[1,2,3,4,5] - 0 breaks. (0 <= 1 is true) ✅
[3,4,5,1,2] - 1 break (5 > 1). (1 <= 1 is true) ✅
[2,1,3,4] - 2 breaks (2 > 1 and 4 > 2 if we consider circularity). (2 <= 1 is false) ❌

This single "break count" idea will be our guiding light!

🪜 Approach: Counting the Descents

Based on our intuition, here's the step-by-step approach:

Initialize a counter: Let's call it count, and set it to 0. This count will keep track of how many times we find nums[i-1] > nums[i].
Iterate through the array (non-circularly): Loop from the second element (i=1) up to the last element (i=n-1).
- In each step, compare nums[i-1] with nums[i].
- If nums[i-1] > nums[i], it means we've found a "descent" or a "break" in the non-decreasing order. Increment count.
Check the "wrap-around" break: After the loop, we need to account for the possibility that the rotation break happens between the last element and the first element.
- Compare nums[n-1] (the last element) with nums[0] (the first element).
- If nums[n-1] > nums[0], it means the "wrap-around" also caused a break. Increment count.
Final Decision:
- If count is 0 or 1, return true. This means the array was originally sorted and rotated (0 rotations for count=0, 1 rotation for count=1).
- If count is greater than 1, return false. This indicates more than one break, meaning the array wasn't a simple sorted-and-rotated sequence.

Let's walk through [2,1,3,4] again with this precise logic:

count = 0
n = 4
Loop:
- i=1: nums[0]=2, nums[1]=1. 2 > 1 is true. count becomes 1.
- i=2: nums[1]=1, nums[2]=3. 1 > 3 is false. count remains 1.
- i=3: nums[2]=3, nums[3]=4. 3 > 4 is false. count remains 1.
After loop: count = 1.
Wrap-around check: nums[n-1]=4, nums[0]=2. 4 > 2 is true. count becomes 2.
Final Decision: count is 2. Since 2 > 1, we return false. Correct!

This approach correctly identifies all the "breaks" in the circular order and gives us the answer!

💻 Code

Here's the C++ implementation using the approach we just discussed:

class Solution {
public:
    bool check(std::vector<int>& nums) {
        int count = 0; // Initialize a counter for "descents" or "breaks"
        int n = nums.size(); // Get the size of the array

        // Step 1: Iterate through the array to find internal breaks
        // We compare nums[i-1] with nums[i]
        // Example: in [3,4,5,1,2], the break 5 > 1 is found here.
        for (int i = 1; i < n; i++) {
            if (nums[i-1] > nums[i]) {
                count++; // Increment count if a descent is found
            }
        }

        // Step 2: Check the "wrap-around" break
        // This handles cases like [1,2,3] where there's no internal break,
        // but if we consider it circularly (3 -> 1), it's a "descent".
        // Also handles the actual rotation point for arrays like [4,5,1,2,3] where 5 > 1 is the break.
        // It complements the loop by checking the (last, first) pair.
        if (nums[n-1] > nums[0]) {
            count++; // Increment count if the wrap-around is a descent
        }

        // Step 3: Determine if the array is sorted and rotated
        // A truly sorted and rotated array (including 0 rotations)
        // will have at most one "break" in the non-decreasing sequence.
        // If count is 0, it's perfectly sorted.
        // If count is 1, it's sorted and rotated once.
        // If count > 1, it's not a sorted and rotated array.
        return count <= 1;
    }
};

⏱️ Time & Space Complexity Analysis

Time Complexity: O(N)
- We iterate through the nums array exactly once in the for loop, which takes O(N) time where N is the number of elements in nums.
- The additional if condition and variable assignments are constant time operations.
- Therefore, the total time complexity is linear with respect to the input array size.
Space Complexity: O(1)
- We only use a few extra variables (count, n) to store our state. These variables take up a constant amount of memory, regardless of the input array's size.
- Thus, the space complexity is constant.

✨ Key Takeaways

The "One Break" Rule: The most crucial insight for this problem is realizing that a sorted array, when rotated, will have at most one point where the non-decreasing order is broken. This single "descent" marks the transition from the largest elements back to the smallest ones.
Circular Thinking: Many array problems, especially those involving rotations, benefit from thinking about the array as a circular structure. Even if you don't explicitly use the modulo operator (i+1)%n, remembering to check the (last, first) pair is vital.
Simple Iteration: A single pass through the array is often enough to gather all the necessary information for many array-based problems.

This problem is a fantastic way to practice identifying patterns in arrays and translating those patterns into clean, efficient code. Keep practicing, and happy coding!

Author: Vansh2710
Published: 2026-03-28 23:13:11