LeetCode Solution: 1752. Check if Array Is Sorted and Rotated
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 tonums[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 > 1is a break. And then3 <= 4is 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]has2>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 wherenums[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 <= 1is true) ✅ -
[3,4,5,1,2]– 1 break (5 > 1). (1 <= 1is true) ✅ -
[2,1,3,4]– 2 breaks (2 > 1and4 > 2if we consider circularity). (2 <= 1is 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 to0. Thiscountwill keep track of how many times we findnums[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]withnums[i]. - If
nums[i-1] > nums[i], it means we’ve found a “descent” or a “break” in the non-decreasing order. Incrementcount.
- In each step, compare
- 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) withnums[0](the first element). - If
nums[n-1] > nums[0], it means the “wrap-around” also caused a break. Incrementcount.
- Compare
- Final Decision:
- If
countis0or1, returntrue. This means the array was originally sorted and rotated (0 rotations forcount=0, 1 rotation forcount=1). - If
countis greater than1, returnfalse. This indicates more than one break, meaning the array wasn’t a simple sorted-and-rotated sequence.
- If
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 > 1is true.countbecomes1. -
i=2:nums[1]=1, nums[2]=3.1 > 3is false.countremains1. -
i=3:nums[2]=3, nums[3]=4.3 > 4is false.countremains1.
-
- After loop:
count = 1. - Wrap-around check:
nums[n-1]=4, nums[0]=2.4 > 2is true.countbecomes2. - Final Decision:
countis2. Since2 > 1, we returnfalse. 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
numsarray exactly once in theforloop, which takesO(N)time whereNis the number of elements innums. - The additional
ifcondition and variable assignments are constant time operations. - Therefore, the total time complexity is linear with respect to the input array size.
- We iterate through the
-
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.
- We only use a few extra variables (
✨ 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
