1752. Check if Array Is Sorted and Rotated - Explanation

Description

You are 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 B[i] == A[(i+x) % A.length] for every valid index i.

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 = 2 positions to begin on 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

Topics

Array

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Array Traversal - Iterating through arrays and comparing adjacent elements
Modulo Arithmetic - Using modulo to handle circular array indexing (wrap-around)
Sorted Array Properties - Understanding non-decreasing order and rotation concepts

1. Brute Force

Intuition

A sorted and rotated array can be thought of as taking a sorted array and moving some elements from the end to the beginning. For example, [3,4,5,1,2] is [1,2,3,4,5] rotated. We can verify this by sorting the array and checking if our original array matches some rotation of the sorted version.

Algorithm

Create a sorted copy of the input array.
Try every possible rotation (0 to n-1 positions).
For each rotation amount i, compare the original array with the sorted array rotated by i positions.
To compare, check elements from position n-i to n-1 of the sorted array against the beginning of the original, then elements from position 0 to n-i-1 against the rest.
If any rotation matches the original array, return true.
If no rotation matches, return false.

class Solution:
    def check(self, nums: List[int]) -> bool:
        sortedNums = sorted(nums)
        arr = []

        for i in range(len(nums)):
            arr.insert(0, sortedNums.pop())
            if nums == arr + sortedNums:
                return True

        return False

public class Solution {
    public boolean check(int[] nums) {
        int n = nums.length;
        int[] sortedNums = nums.clone();
        Arrays.sort(sortedNums);

        for (int i = 0; i < n; i++) {
            boolean match = true;
            int idx = 0;
            for (int j = n - i; j < n && match; j++) {
                if (nums[idx] != sortedNums[j]) {
                    match = false;
                }
                idx += 1;
            }

            for (int j = 0; j < n - i && match; j++) {
                if (nums[idx] != sortedNums[j]) {
                    match = false;
                }
                idx += 1;
            }

            if (match) return true;
        }

        return false;
    }
}

class Solution {
public:
    bool check(vector<int>& nums) {
        int n = nums.size();
        vector<int> sortedNums = nums;
        sort(sortedNums.begin(), sortedNums.end());

        for (int i = 0; i < n; i++) {
            bool match = true;
            int idx = 0;
            for (int j = n - i; j < n && match; j++) {
                if (nums[idx] != sortedNums[j]) {
                    match = false;
                }
                idx++;
            }

            for (int j = 0; j < n - i && match; j++) {
                if (nums[idx] != sortedNums[j]) {
                    match = false;
                }
                idx++;
            }

            if (match) return true;
        }

        return false;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {boolean}
     */
    check(nums) {
        const n = nums.length;
        const sortedNums = [...nums].sort((a, b) => a - b);

        for (let i = 0; i < n; i++) {
            let match = true;
            let idx = 0;

            for (let j = n - i; j < n && match; j++) {
                if (nums[idx] !== sortedNums[j]) {
                    match = false;
                }
                idx++;
            }

            for (let j = 0; j < n - i && match; j++) {
                if (nums[idx] !== sortedNums[j]) {
                    match = false;
                }
                idx++;
            }

            if (match) return true;
        }

        return false;
    }
}

public class Solution {
    public bool Check(int[] nums) {
        int n = nums.Length;
        int[] sortedNums = (int[])nums.Clone();
        Array.Sort(sortedNums);

        for (int i = 0; i < n; i++) {
            bool match = true;
            int idx = 0;

            for (int j = n - i; j < n && match; j++) {
                if (nums[idx] != sortedNums[j]) {
                    match = false;
                }
                idx++;
            }

            for (int j = 0; j < n - i && match; j++) {
                if (nums[idx] != sortedNums[j]) {
                    match = false;
                }
                idx++;
            }

            if (match) return true;
        }

        return false;
    }
}

func check(nums []int) bool {
    n := len(nums)
    sortedNums := make([]int, n)
    copy(sortedNums, nums)
    sort.Ints(sortedNums)

    for i := 0; i < n; i++ {
        match := true
        idx := 0

        for j := n - i; j < n && match; j++ {
            if nums[idx] != sortedNums[j] {
                match = false
            }
            idx++
        }

        for j := 0; j < n-i && match; j++ {
            if nums[idx] != sortedNums[j] {
                match = false
            }
            idx++
        }

        if match {
            return true
        }
    }

    return false
}

class Solution {
    fun check(nums: IntArray): Boolean {
        val n = nums.size
        val sortedNums = nums.clone()
        sortedNums.sort()

        for (i in 0 until n) {
            var match = true
            var idx = 0

            var j = n - i
            while (j < n && match) {
                if (nums[idx] != sortedNums[j]) {
                    match = false
                }
                idx++
                j++
            }

            j = 0
            while (j < n - i && match) {
                if (nums[idx] != sortedNums[j]) {
                    match = false
                }
                idx++
                j++
            }

            if (match) return true
        }

        return false
    }
}

class Solution {
    func check(_ nums: [Int]) -> Bool {
        let n = nums.count
        let sortedNums = nums.sorted()

        for i in 0..<n {
            var match = true
            var idx = 0

            var j = n - i
            while j < n && match {
                if nums[idx] != sortedNums[j] {
                    match = false
                }
                idx += 1
                j += 1
            }

            j = 0
            while j < n - i && match {
                if nums[idx] != sortedNums[j] {
                    match = false
                }
                idx += 1
                j += 1
            }

            if match { return true }
        }

        return false
    }
}

impl Solution {
    pub fn check(nums: Vec<i32>) -> bool {
        let n = nums.len();
        let mut sorted_nums = nums.clone();
        sorted_nums.sort();

        for i in 0..n {
            let mut matched = true;
            let mut idx = 0;

            let mut j = n - i;
            while j < n && matched {
                if nums[idx] != sorted_nums[j] {
                    matched = false;
                }
                idx += 1;
                j += 1;
            }

            j = 0;
            while j < n - i && matched {
                if nums[idx] != sorted_nums[j] {
                    matched = false;
                }
                idx += 1;
                j += 1;
            }

            if matched { return true; }
        }

        false
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Sliding Window

Intuition

If we imagine the array as circular (the last element connects back to the first), a valid sorted-and-rotated array should have a contiguous segment of length n where elements are in non-decreasing order. We can simulate this circular behavior by conceptually doubling the array and looking for n consecutive non-decreasing elements.

Algorithm

Iterate through indices 1 to 2n-1, treating the array as circular using modulo operations.
Maintain a count of consecutive non-decreasing pairs.
If the current element (at index i % n) is greater than or equal to the previous element, increment the count.
Otherwise, reset the count to 1.
If at any point the count reaches n, we found a valid sorted sequence, so return true.
Handle the edge case where n equals 1 by returning true at the end.

class Solution:
    def check(self, nums: List[int]) -> bool:
        N = len(nums)
        count = 1

        for i in range(1, 2 * N):
            if nums[(i - 1) % N] <= nums[i % N]:
                count += 1
            else:
                count = 1
            if count == N:
                return True

        return N == 1

class Solution {
    /**
     * @param {number[]} nums
     * @return {boolean}
     */
    check(nums) {
        const N = nums.length;
        let count = 1;

        for (let i = 1; i < 2 * N; i++) {
            if (nums[(i - 1) % N] <= nums[i % N]) {
                count++;
            } else {
                count = 1;
            }
            if (count === N) {
                return true;
            }
        }

        return N === 1;
    }
}

func check(nums []int) bool {
    N := len(nums)
    count := 1

    for i := 1; i < 2*N; i++ {
        if nums[(i-1)%N] <= nums[i%N] {
            count++
        } else {
            count = 1
        }
        if count == N {
            return true
        }
    }

    return N == 1
}

class Solution {
    fun check(nums: IntArray): Boolean {
        val N = nums.size
        var count = 1

        for (i in 1 until 2 * N) {
            if (nums[(i - 1) % N] <= nums[i % N]) {
                count++
            } else {
                count = 1
            }
            if (count == N) {
                return true
            }
        }

        return N == 1
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

3. Iteration

Intuition

In a sorted-and-rotated array, there can be at most one "break point" where a larger element is followed by a smaller element. This break point is where the rotation occurred. If we find more than one such break, the array cannot be a valid rotation of a sorted array.

Algorithm

Initialize a counter for the number of break points (where an element is greater than its next element).
Iterate through the array, comparing each element with the next one (using modulo to wrap around from the last element to the first).
If the current element is greater than the next element, increment the break counter.
If the counter exceeds 1 at any point, return false immediately.
After checking all pairs, return true (at most one break was found).

class Solution:
    def check(self, nums: List[int]) -> bool:
        count, N = 0, len(nums)

        for i in range(N):
            if nums[i] > nums[(i + 1) % N]:
                count += 1
                if count > 1:
                    return False

        return True

class Solution {
    /**
     * @param {number[]} nums
     * @return {boolean}
     */
    check(nums) {
        let count = 0,
            N = nums.length;

        for (let i = 0; i < N; i++) {
            if (nums[i] > nums[(i + 1) % N] && ++count > 1) {
                return false;
            }
        }

        return true;
    }
}

func check(nums []int) bool {
    count, N := 0, len(nums)

    for i := 0; i < N; i++ {
        if nums[i] > nums[(i+1)%N] {
            count++
            if count > 1 {
                return false
            }
        }
    }

    return true
}

class Solution {
    fun check(nums: IntArray): Boolean {
        var count = 0
        val N = nums.size

        for (i in 0 until N) {
            if (nums[i] > nums[(i + 1) % N]) {
                count++
                if (count > 1) {
                    return false
                }
            }
        }

        return true
    }
}

class Solution {
    func check(_ nums: [Int]) -> Bool {
        var count = 0
        let N = nums.count

        for i in 0..<N {
            if nums[i] > nums[(i + 1) % N] {
                count += 1
                if count > 1 {
                    return false
                }
            }
        }

        return true
    }
}

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;
                if count > 1 {
                    return false;
                }
            }
        }

        true
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Forgetting to Check the Wrap-Around

A sorted and rotated array is circular, so you must compare the last element with the first element. Using nums[i] > nums[i + 1] without modulo wrapping misses the case where the "break" occurs between the last and first elements.

# Wrong: if nums[i] > nums[i + 1]
# Correct:
if nums[i] > nums[(i + 1) % N]

Expecting Strictly Increasing Order

The problem allows non-decreasing order (duplicates are permitted). Checking for strict inequality nums[i] >= nums[i+1] instead of nums[i] > nums[i+1] incorrectly flags valid arrays like [1, 1, 1] or [2, 2, 3, 1, 1] as invalid.