Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Check if Array Is Sorted and Rotated

EASYProblemSolveExternal Links

Description

Given an integer array nums, return true if the array was originally sorted in non-decreasing order and then rotated some number of positions (including zero rotations). Otherwise, return false.

A rotation takes some number of elements from the beginning and moves them to the end (or equivalently, shifts everything left by some positions circularly). For example, [1, 2, 3, 4, 5] rotated by 2 positions becomes [3, 4, 5, 1, 2].

The array may contain duplicate values.

Note: An array A rotated by x positions results in an array B of the same length such that B[i] == A[(i + x) % A.length] for every valid index i.

Examples

Example 1

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

Output: true

Explanation: The original sorted array is [1, 2, 3, 4, 5]. If we rotate it by 3 positions to the right (or equivalently 2 positions to the left), we get [3, 4, 5, 1, 2]. The transition from 5 to 1 is the single "drop" point where the sorted order breaks, which is consistent with exactly one rotation point.

Example 2

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

Output: false

Explanation: There is no sorted array that, when rotated, produces [2, 1, 3, 4]. We see a drop from 2 to 1 (at index 0→1), and then the array rises from 1 to 4. But notice the last element 4 is greater than the first element 2 — that means the "wrap-around" from the end to the beginning also breaks sorted order. Two breaks means this cannot come from a single rotation of a sorted array.

Example 3

Input: nums = [1, 2, 3]

Output: true

Explanation: The array [1, 2, 3] is already sorted in non-decreasing order. This corresponds to rotating the sorted array by 0 positions (no rotation at all). Since there are zero drops in the sequence, it qualifies as a sorted-and-rotated array.

Constraints

  • 1 ≤ nums.length ≤ 100
  • 1 ≤ nums[i] ≤ 100

Editorial

Brute Force

Intuition

The most straightforward way to verify if the array is a rotated version of a sorted array is to literally try every possible rotation.

Imagine you have a circular turntable with the array elements placed around it. You try spinning the turntable to each of the n possible positions and checking: "Does the array read in sorted order from this starting position?" If any rotation produces a sorted sequence, the answer is true.

Concretely, for each possible rotation amount r (from 0 to n-1), we construct what the sorted array would look like if it were rotated by r positions, and compare it against nums. Alternatively, we can sort a copy of the array and then try all rotations of that sorted copy to see if any matches nums.

Step-by-Step Explanation

Let's trace through with nums = [3, 4, 5, 1, 2]:

Step 1: Sort a copy of nums to get the expected sorted array.

  • sorted_arr = [1, 2, 3, 4, 5]

Step 2: Try rotation r = 0.

  • Rotated sorted: [1, 2, 3, 4, 5]
  • Compare with nums [3, 4, 5, 1, 2]: Does NOT match.

Step 3: Try rotation r = 1.

  • Rotated sorted: [2, 3, 4, 5, 1]
  • Compare with nums [3, 4, 5, 1, 2]: Does NOT match.

Step 4: Try rotation r = 2.

  • Rotated sorted: [3, 4, 5, 1, 2]
  • Compare with nums [3, 4, 5, 1, 2]: Does NOT match at first glance... wait, let's check element by element.
  • Index 0: 3 == 3 ✓
  • Index 1: 4 == 4 ✓
  • Index 2: 5 == 5 ✓
  • Index 3: 1 == 1 ✓
  • Index 4: 2 == 2 ✓
  • All elements match! This rotation works.

Step 5: Return true — we found rotation r = 2 that produces nums from the sorted array.

For nums = [2, 1, 3, 4], the sorted array is [1, 2, 3, 4]. No rotation of [1, 2, 3, 4] produces [2, 1, 3, 4], so we return false after trying all 4 rotations.

Brute Force — Try Every Rotation of the Sorted Array — Watch as we sort the array and try each rotation, comparing element-by-element against the input until we find a match.

Algorithm

  1. Create a sorted copy of the input array
  2. For each possible rotation amount r from 0 to n-1:
    a. For each index i from 0 to n-1:
    • Compare nums[i] with sorted_arr[(i + r) % n]
    • If they differ, this rotation doesn't work; break and try next r
      b. If all n elements matched, return true
  3. If no rotation matched, return false

Code

class Solution {
public:
    bool check(vector<int>& nums) {
        int n = nums.size();
        vector<int> sorted_arr = nums;
        sort(sorted_arr.begin(), sorted_arr.end());
        
        for (int r = 0; r < n; r++) {
            bool match = true;
            for (int i = 0; i < n; i++) {
                if (nums[i] != sorted_arr[(i + r) % n]) {
                    match = false;
                    break;
                }
            }
            if (match) return true;
        }
        return false;
    }
};
class Solution:
    def check(self, nums: list[int]) -> bool:
        n = len(nums)
        sorted_arr = sorted(nums)
        
        for r in range(n):
            match = True
            for i in range(n):
                if nums[i] != sorted_arr[(i + r) % n]:
                    match = False
                    break
            if match:
                return True
        return False
class Solution {
    public boolean check(int[] nums) {
        int n = nums.length;
        int[] sortedArr = nums.clone();
        Arrays.sort(sortedArr);
        
        for (int r = 0; r < n; r++) {
            boolean match = true;
            for (int i = 0; i < n; i++) {
                if (nums[i] != sortedArr[(i + r) % n]) {
                    match = false;
                    break;
                }
            }
            if (match) return true;
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(n²)

Sorting takes O(n log n). Then we try up to n rotations, and for each rotation we compare up to n elements. The comparison phase dominates: n rotations × n comparisons = O(n²). Combined: O(n log n + n²) = O(n²).

Space Complexity: O(n)

We create a sorted copy of the array, which takes O(n) additional space.

Why This Approach Is Not Efficient

The brute force approach tries all n rotations and compares the full array for each, leading to O(n²) time. While n ≤ 100 in this problem makes it feasible, the approach is fundamentally wasteful.

The core insight we are missing: a sorted-and-rotated array has a very specific structural property. When you look at consecutive element pairs in the array (including wrapping from the last element to the first), a sorted-and-rotated array can have at most one place where the value decreases (the "inversion" or "break point"). This is because the rotation creates exactly one spot where the end of the original sorted array wraps around to the beginning.

Instead of constructing and comparing full rotations, we can simply count how many times the sequence "drops" (where nums[i] > nums[i+1] circularly). If there is at most one drop, the array is sorted and rotated. This observation eliminates the need for sorting and reduces the problem to a single pass.

Optimal Approach - Count Inversions

Intuition

Think of the array as arranged in a circle (the last element connects to the first). In a perfectly sorted array, every element is less than or equal to the next one — there are zero drops as you walk around the circle.

When you rotate a sorted array, you introduce exactly one drop: the spot where the end of the original sorted sequence meets the beginning. For example, in [3, 4, 5, 1, 2], the only drop is from 5 to 1.

So the key observation is:

  • 0 drops → The array is already sorted (rotation by 0). Return true.
  • 1 drop → The array has exactly one rotation point. But we also need to verify that the wrap-around is valid: the last element must be ≤ the first element. Return true.
  • 2+ drops → The array cannot be a rotation of any sorted array. Return false.

The elegant trick: if we check nums[i] > nums[(i+1) % n] for all indices (using modular arithmetic to wrap from the last element to the first), we naturally handle the wrap-around check. If the total count of such inversions is ≤ 1, the answer is true.

Step-by-Step Explanation

Let's trace through with nums = [3, 4, 5, 1, 2]:

Step 1: Initialize count = 0. We will check each adjacent pair circularly.

Step 2: Compare nums[0]=3 and nums[1]=4.

  • Is 3 > 4? No. This is not a drop.
  • count remains 0.

Step 3: Compare nums[1]=4 and nums[2]=5.

  • Is 4 > 5? No. Not a drop.
  • count remains 0.

Step 4: Compare nums[2]=5 and nums[3]=1.

  • Is 5 > 1? YES! This is a drop — the sequence decreases.
  • count = 1.

Step 5: Compare nums[3]=1 and nums[4]=2.

  • Is 1 > 2? No. Not a drop.
  • count remains 1.

Step 6: Compare nums[4]=2 and nums[0]=3 (wrap-around using modular arithmetic).

  • Is 2 > 3? No. The last element flows smoothly into the first.
  • count remains 1.

Step 7: Final check: count = 1 ≤ 1, so return true.

Now let's verify with nums = [2, 1, 3, 4]:

  • (2,1): 2 > 1? Yes → count = 1
  • (1,3): No
  • (3,4): No
  • (4,2) wrap: 4 > 2? Yes → count = 2
  • count = 2 > 1 → return false.

Count Inversions — Single Pass with Circular Wrap — Watch as we scan adjacent pairs (including the wrap-around from last to first) and count how many times the value drops. At most 1 drop means sorted-and-rotated.

Algorithm

  1. Initialize a counter count = 0
  2. For each index i from 0 to n-1:
    • Compare nums[i] with nums[(i + 1) % n] (using modular arithmetic for wrap-around)
    • If nums[i] > nums[(i + 1) % n], increment count
  3. If count ≤ 1, return true (the array is sorted and rotated)
  4. Otherwise, return false

Code

class Solution {
public:
    bool check(vector<int>& nums) {
        int n = nums.size();
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] > nums[(i + 1) % n]) {
                count++;
            }
        }
        
        return count <= 1;
    }
};
class Solution:
    def check(self, nums: list[int]) -> bool:
        n = len(nums)
        count = 0
        
        for i in range(n):
            if nums[i] > nums[(i + 1) % n]:
                count += 1
        
        return count <= 1
class Solution {
    public boolean check(int[] nums) {
        int n = nums.length;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] > nums[(i + 1) % n]) {
                count++;
            }
        }
        
        return count <= 1;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the array exactly once, checking each of the n adjacent pairs (including the circular wrap from the last element to the first). Each comparison is an O(1) operation. Total: O(n).

Space Complexity: O(1)

We only use a single integer variable count to track the number of drops. No additional data structures are created, so space usage is constant regardless of input size.