Check if Array Is Sorted and Rotated
Problem link: https://leetcode.com/problems/check-if-array-is-sorted-and-rotated/
Problem Statement
Given an array nums, return true if the array was originally sorted in non-decreasing order, then rotated some number of positions. Otherwise, return false.
There may be duplicates in the original array.
Input
An integer array nums.
Output
Boolean (true or false).
Example
Input: nums = [3,4,5,1,2] Output: true Explanation: The sorted array [1,2,3,4,5] was rotated 3 times to become [3,4,5,1,2].
Explanation
In a sorted and rotated array, if you look at it circularly, there should be at most one place where a number is greater than the next number.
Brute Force
Intuition
Try every possible rotation. For an array of size N, check all N rotations to see if any of them are sorted.
Approach
- Loop through all possible rotation offsets.
- For each offset, construct the rotated array.
- Verify if the rotated array is sorted in non-decreasing order.
- Return true if any rotation works.
Dry Run
nums = [2,1,3] Rot 0: [2,1,3] -> No Rot 1: [1,3,2] -> No Rot 2: [3,2,1] -> No Result: false
Code (Java)
class Solution {
public boolean check(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
boolean sorted = true;
for (int j = 0; j < n - 1; j++) {
if (nums[(i + j) % n] > nums[(i + j + 1) % n]) {
sorted = false;
break;
}
}
if (sorted) return true;
}
return false;
}
}
Complexity Analysis
We check N rotations, and each check takes O(N) time.
Optimal Solution
Intuition
A sorted array has 0 breaks where a number is larger than the next. A sorted and rotated array has exactly 1 break. By checking the array circularly (including the last element compared to the first), we simply count these breaks.
Approach
- Initialize count = 0.
- Iterate through the array from i = 0 to N-1.
- Compare nums[i] with the next element using (i + 1) % N to include the wrap-around.
- If nums[i] > nums[next], increment count.
- Return true if count is 1 or 0.
Dry Run
nums = [3,4,5,1,2] 3 > 4: No 4 > 5: No 5 > 1: Yes (count=1) 1 > 2: No 2 > 3: No Final count = 1 -> True
Code (Java)
class Solution {
public boolean check(int[] nums) {
int count = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
if (nums[i] > nums[(i + 1) % n]) {
count++;
}
}
return count <= 1;
}
}
Complexity Analysis
We traverse the array once, performing a constant time comparison at each step.
Quick Revision (Brute Force)
- Generate all rotations
- Check each for sorted order
- O(N^2) time
Quick Revision (Optimal)
- Count drops circularly
- Use (i+1)%n for wrap-around
- True if drops <= 1
- O(N) time