1752. Check if Array Is Sorted and Rotated

The problem

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

There may be duplicates in the original array.

Note: An array A rotated by x positions results in an array B of the same length such that A[i] == B[(i+x) % A.length], where % is the modulo operation.

Example 1:

Input: nums = [3,4,5,1,2]
Output: true
Explanation: [1,2,3,4,5] is the original sorted array.
You can rotate the array by x = 3 positions to begin on the the element of value 3: [3,4,5,1,2].

Example 2:

Input: nums = [2,1,3,4]
Output: false
Explanation: There is no sorted array once rotated that can make nums.

Example 3:

Input: nums = [1,2,3]
Output: true
Explanation: [1,2,3] is the original sorted array.
You can rotate the array by x = 0 positions (i.e. no rotation) to make nums.

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

Approach overview

Problem Overview: You are given an integer array. The task is to check whether the array was originally sorted in non-decreasing order and then rotated some number of times. A valid rotated sorted array can have at most one position where the order decreases.

Approach 1: Simulate Rotation (O(n²) time, O(1) space)

The brute force idea is to simulate every possible rotation and check whether the resulting array is sorted. For each rotation index k, construct the rotated order and verify that every element is less than or equal to the next element while iterating through the array. If any rotation produces a sorted sequence, the array satisfies the condition. This approach directly models the definition of rotation but performs a full sorted check for each shift, leading to O(n²) time complexity.

Approach 2: Count Break Points (O(n) time, O(1) space)

A rotated sorted array has a key property: there can be at most one index where nums[i] > nums[i+1]. This position is the rotation pivot. Iterate through the array and count such "break points". Because rotation wraps around, also compare the last and first elements. If the number of breaks is more than one, the array cannot be a rotated sorted array. The algorithm performs a single pass through the array, keeping a counter and checking adjacent values, which makes it efficient and interview-friendly.

The core insight is treating the array as circular. In a perfectly sorted array there are zero decreases, while in a rotated sorted array there is exactly one. This observation eliminates the need for explicitly rotating the array or rebuilding structures.

Recommended for interviews: The break-point counting approach is what interviewers expect. It shows you recognize the structural property of a rotated sorted array and can solve the problem in O(n) time with constant space. Discussing the brute-force rotation check first demonstrates understanding of the problem definition, but implementing the single-pass solution highlights stronger algorithmic thinking.

Approach 1: Count Break Points

In a rotated sorted array, there should be exactly one point where a number is greater than its subsequent number, marking the 'rotation break'. We iterate over the array to count how many such breaks exist.

Python

class Solution:
    def check(self, nums):
        count = 0
        n = len(nums)
        for i in range(n):
            if nums[i] > nums[(i + 1) % n]:
                count += 1
        return count <= 1

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;
    }
}

C++

#include <vector>
using namespace std;

class Solution {
public:
    bool check(vector<int>& nums) {
        int count = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] > nums[(i + 1) % n]) {
                count++;
            }
        }
        return count <= 1;
    }
};

JavaScript

function check(nums) {
    let count = 0;
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        if (nums[i] > nums[(i + 1) % n]) {
            count++;
        }
    }
    return count <= 1;
}

#include <stdbool.h>

bool check(int* nums, int numsSize) {
    int count = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > nums[(i + 1) % numsSize]) {
            count++;
        }
    }
    return count <= 1;
}

public class Solution {
    public bool 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;
    }
}

By iterating over the list, we detect if there are more than one inversion (nums[i] > nums[i+1]). The modulo operation allows cyclic comparisons.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Simulate Rotation

This approach involves simulating the rotation of a sorted version of the input array and checking if it matches the original array. This is done by sorting the array, and then checking each possible rotation for a match.

Python

class Solution:
    def check(self, nums):
        sorted_nums = sorted(nums)
        n = len(nums)
        for start in range(n):
            if all(sorted_nums[i] == nums[(start + i) % n] for i in range(n)):
                return True
        return False

Java

import java.util.Arrays;

class Solution {
    public boolean check(int[] nums) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        int n = nums.length;
        for (int start = 0; start < n; start++) {
            boolean match = true;
            for (int i = 0; i < n; i++) {
                if (sorted[i] != nums[(start + i) % n]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                return true;
            }
        }
        return false;
    }
}

C++

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    bool check(vector<int>& nums) {
        vector<int> sorted(nums);
        sort(sorted.begin(), sorted.end());
        int n = nums.size();
        for (int start = 0; start < n; start++) {
            bool match = true;
            for (int i = 0; i < n; i++) {
                if (sorted[i] != nums[(start + i) % n]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                return true;
            }
        }
        return false;
    }
};

JavaScript

function check(nums) {
    const sorted = [...nums].sort((a, b) => a - b);
    const n = nums.length;
    for (let start = 0; start < n; start++) {
        if (sorted.every((val, i) => val === nums[(start + i) % n])) {
            return true;
        }
    }
    return false;
}

#include <stdbool.h>
#include <stdlib.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

bool check(int* nums, int numsSize) {
    int* sorted = malloc(sizeof(int) * numsSize);
    for (int i = 0; i < numsSize; i++) {
        sorted[i] = nums[i];
    }
    qsort(sorted, numsSize, sizeof(int), compare);
    for (int start = 0; start < numsSize; start++) {
        bool match = true;
        for (int i = 0; i < numsSize; i++) {
            if (sorted[i] != nums[(start + i) % numsSize]) {
                match = false;
                break;
            }
        }
        if (match) {
            free(sorted);
            return true;
        }
    }
    free(sorted);
    return false;
}

using System;

public class Solution {
    public bool Check(int[] nums) {
        int[] sorted = (int[])nums.Clone();
        Array.Sort(sorted);
        int n = nums.Length;
        for (int start = 0; start < n; start++) {
            bool match = true;
            for (int i = 0; i < n; i++) {
                if (sorted[i] != nums[(start + i) % n]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                return true;
            }
        }
        return false;
    }
}

Python leverages its list comprehensions to check rotation matchings. The array is first sorted, and then all potential rotations are tested to find a match with the initial list.

Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function check(nums: number[]): boolean {
    const n = nums.length;
    return nums.reduce((r, v, i) => r + (v > nums[(i + 1) % n] ? 1 : 0), 0) <= 1;
}

func check(nums []int) bool {
	cnt := 0
	for i, v := range nums {
		if v > nums[(i+1)%len(nums)] {
			cnt++
		}
	}
	return cnt <= 1
}

Rust

impl Solution {
    pub fn check(nums: Vec<i32>) -> bool {
        let n = nums.len();
        let mut count = 0;
        for i in 0..n {
            if nums[i] > nums[(i + 1) % n] {
                count += 1;
            }
        }
        count <= 1
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Count Break Points	Time Complexity: O(n) Space Complexity: O(1)
Simulate Rotation	Time Complexity: O(n^2) Space Complexity: O(n)
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Simulate Rotation	O(n²)	O(1)	Useful for understanding the definition of rotation or when demonstrating the brute-force baseline
Count Break Points	O(n)	O(1)	Best approach for interviews and production due to linear scan and constant memory

Frequently asked questions

Is Check if Array Is Sorted and Rotated easy or hard?

The problem is classified as Easy on LeetCode. The main challenge is recognizing that a rotated sorted array can only have one decreasing pair. Once that insight is clear, the implementation becomes a straightforward O(n) scan.

Check if Array Is Sorted and Rotated Python/Java solution

The typical implementation iterates through the array and increments a counter whenever nums[i] > nums[i+1]. After the loop, compare nums[n-1] with nums[0] for the circular condition. This logic works identically in Python, Java, C++, JavaScript, and other languages.

How to solve Check if Array Is Sorted and Rotated in O(n)?

Traverse the array and count how many times the order decreases, meaning nums[i] > nums[i+1]. Also check the circular pair nums[n-1] and nums[0]. If the number of decreases is greater than one, the array is not a rotated sorted array. Otherwise it satisfies the condition.

What is the best approach for Check if Array Is Sorted and Rotated?

The most efficient approach is counting break points in the array. Iterate once and count positions where nums[i] > nums[i+1], including the circular comparison between the last and first element. A valid rotated sorted array has at most one such drop. This solution runs in O(n) time and O(1) space.

Is Check if Array Is Sorted and Rotated asked at Google/Amazon/Meta?

Variants of rotated array checks appear in interviews at companies like Amazon, Google, and Meta, usually as warm-up array problems. They test whether you can identify structural properties in arrays and reduce the problem to a single linear pass.

What data structure is used in Check if Array Is Sorted and Rotated?

The problem primarily uses a simple array traversal. No additional data structures such as hash maps or stacks are required. The optimal solution relies on sequential comparison of neighboring elements in the array.

What is the time complexity of Check if Array Is Sorted and Rotated?

The optimal solution runs in O(n) time because it scans the array once and compares adjacent elements. Space complexity is O(1) since only a counter variable is used. A brute-force rotation simulation would take O(n²) time.

Check if Array Is Sorted and Rotated solution and explanation

The problem

Approach overview

Approach 1: Count Break Points

Approach 2: Simulate Rotation

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Check if Array Is Sorted and Rotated solution and explanation

The problem

Approach overview

Approach 1: Count Break Points

Approach 2: Simulate Rotation

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems