Check if Array Is Sorted and Rotated

easy array rotation

Problem

You are given an integer array nums. Decide whether it could have been produced by taking some array sorted in non-decreasing order and rotating it: every element shifts right by the same offset and the tail wraps around to the front. A rotation by zero positions counts, and duplicate values are allowed (1 ≤ nums[i] ≤ 100).

Formally, return true exactly when there exist a sorted array B and an offset x with nums[i] = B[(i + x) mod n] for every index i.

Inputnums = [3, 4, 5, 1, 2]

Outputtrue

It is [1, 2, 3, 4, 5] rotated by 3: going around the circle there is exactly one drop, 5 → 1.

nums (comma-separated integers 1..100)

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

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

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

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

Explanation

The key insight is that rotating a sorted array keeps almost all of its order intact. Order can only break at one place: the seam where the largest values wrap around and meet the smallest. So if we walk the array as a circle — comparing each element to the next, including the last element back to the first — a sorted-then-rotated array shows at most one drop, a position where a value is greater than its successor.

That turns the whole problem into counting. For every index i we compare nums[i] with nums[(i + 1) % n]; the modulo is what closes the circle, making the final comparison wrap from the last element to the first. Each time the left value is strictly greater, we increment count. At the end we return count <= 1.

Walk through the default example [3, 4, 5, 1, 2]: 3 ≤ 4 and 4 ≤ 5 are fine, 5 > 1 is a drop (count = 1), 1 ≤ 2 is fine, and the wrap comparison 2 ≤ 3 is fine too. One drop total, so the answer is true — indeed it is [1, 2, 3, 4, 5] rotated by three positions.

Why is the condition exact? If count = 0 the array is already sorted, which is a rotation by zero. If count = 1, the single drop marks the seam: cutting the circle there and reading forward yields a non-decreasing sequence, so some rotation sorts it. If count ≥ 2 the circle has two seams, which no single rotation of one sorted array can produce.

Duplicates need no special handling because "sorted" means non-decreasing: equal neighbors are not a drop. For instance [2, 1, 2] has only the drop 2 > 1 and is [1, 2, 2] rotated by one.

The loop touches each of the n circular pairs exactly once, giving O(n) time, and it keeps only the counter, so the extra space is O(1).

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