1752. Check If Array Is Sorted And Rotated

1752. Check If Array Is Sorted and Rotated: A Complete Algorithmic Guide

In the competitive landscape of data structures and algorithms, the task to check if array is sorted and rotated is a classic problem that tests your understanding of circular shifts and boundary conditions. This specific challenge, often referenced as LeetCode problem 1752, asks you to determine whether a given integer array was originally sorted in non-decreasing order and then rotated some number of times. While it may appear simple at first glance, the wrap-around logic between the last and first elements introduces subtle traps that can cause even experienced developers to fail. Mastering this concept not only helps you solve a specific coding interview question but also strengthens your intuition for handling circular buffers and modular arithmetic in software engineering.

Understanding the Core Problem

To solve this effectively, you must first visualize what a rotation actually does to a data structure. But imagine a line of people standing in height order, from shortest to tallest. If you ask the first person to walk around to the back of the line, the order changes, but the relative sequence remains intact. In programming terms, an array like [1, 2, 3, 4, 5] becomes [4, 5, 1, 2, 3] after a right rotation of two positions.

The problem defines a valid state as one where the array is sorted and then rotated between zero and n times. This means there are two valid scenarios:

No Rotation: The array is already perfectly sorted, such as [1, 2, 3, 4, 5].

…and the sequence resumes in non‑decreasing order after that point. Practically speaking, in other words, there can be at most one index i such that nums[i] > nums[(i+1) % n]. If zero such indices exist, the array is fully sorted (no rotation); if exactly one exists, the array is a rotated version of a sorted list; more than one break point guarantees that the array cannot be obtained by a single rotation of a sorted sequence.

Linear Scan Solution

The most straightforward way to verify the condition is a single pass over the array:

Initialise a counter breaks = 0.
Iterate i from 0 to n‑1.
- Compare nums[i] with nums[(i+1) % n].
- If nums[i] > nums[(i+1) % n], increment breaks.
- Early‑exit if breaks exceeds 1 (no need to continue).
After the loop, return true if breaks ≤ 1, otherwise false.

Because the comparison uses modulo indexing, the wrap‑around between the last and first elements is handled naturally, eliminating the need for special‑case code.

Handling Duplicates

The problem statement allows non‑decreasing order, so equal adjacent values are permissible. The comparison > (strictly greater) ensures that equal elements do not contribute to a break point, which preserves correctness for inputs like [2,2,2,1,2] (one break at 2 > 1) and [1,1,1] (zero breaks).

Complexity Analysis

Time: O(n) – each element is inspected once.
Space: O(1) – only a few integer variables are used irrespective of input size.

Reference Implementations

Python 3

def check_sorted_and_rotated(nums):
    n = len(nums)
    breaks = 0
    for i in range(n):
        if nums[i] > nums[(i + 1) % n]:
            breaks += 1
            if breaks > 1:
                return False
    return True

Java

class Solution {
    public boolean check(int[] nums) {
        int n = nums.length;
        int breaks = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] > nums[(i + 1) % n]) {
                if (++breaks > 1) return false;
            }
        }
        return true;
    }
}

C++

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

Why This Works

A sorted array rotated any number of times preserves the cyclic order of its elements. As a result, when traversing the circle, you will encounter at most one descent (a place where the next element is smaller). Detecting more than one descent proves that the original ordering was disrupted in more than one place, which cannot be the result of a single rotation. Conversely, zero or one descent exactly matches the two permissible configurations: a fully sorted array (zero descents) or a sorted array that has been cut and re‑attached (one descent).

Conclusion

The “check if array is sorted and rotated” problem reduces to counting the number of times an element exceeds its successor in a circular scan. A single linear pass with O(1) extra space yields an optimal solution that handles edge cases such as empty arrays, single‑element arrays, and duplicate values with ease. Mastering this pattern not only solves LeetCode 1752 but also equips you with a reusable technique for any problem involving circularly shifted sorted sequences.

1752. Check If Array Is Sorted And Rotated