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. The2, 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! Adescent!) -
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 wouldneverget[2,1,3,4]
. A single rotation implies thatallelements after the rotation point are smaller thanallelements 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 itdescentCount
, and set it to0
. This counter will track how many times we findnums[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. IncrementdescentCount
.
- In each iteration, compare the current element (
Check the wrap-around case: After the loop finishes, we need to consider the connection between thelastelement and thefirstelement. 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 is2
) is less thannums[0]
(which is3
). This doesn't add a descent.
However, in[1,2,3]
(0 rotations),nums[2]
(3) is greater thannums[0]
(1).
Let's re-evaluate: The descent is where the sequencedecreases.-
[3, 4, 5, 1, 2]
->5 > 1
(1 descent)-
nums[n-1]
(2) isnotgreater thannums[0]
(3).
[1, 2, 3]
-> No descents.-
nums[n-1]
(3) isnotgreater thannums[0]
(1).
[2, 1, 3, 4]
->2 > 1
(1 descent)-
nums[n-1]
(4) isnotgreater thannums[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) isfalse
. - Total
descentCount = 1
. Returntrue
. Correct.
-
Loop:
* `[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, ifdescentCount
is less than or equal to1
, it means the arraycould have beensorted and rotated. Returntrue
. Otherwise, ifdescentCount
is greater than1
, it means there are too many "breaks" in the sorted order for it to be a single rotation of a sorted array. Returnfalse
.
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 takesO(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