Check if Array Is Sorted and Rotated: Counting Inversions

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

This is LeetCode 1752: Check if Array Is Sorted and Rotated, and it is one of the cleanest examples of how a single observation can reduce a problem to a few lines of code.

Why this problem matters

Rotated sorted arrays show up everywhere in interview prep. You will encounter them in binary search problems like "Search in Rotated Sorted Array" and "Find Minimum in Rotated Sorted Array." Before you can search efficiently in a rotated array, you need to understand what makes one valid in the first place. This problem isolates that question: given an array, is it sorted and rotated?

The technique here, counting order violations, is a building block you can reuse whenever you need to verify a structural property of an array in a single pass.

The key insight

A sorted array has zero "breaks," meaning every element is less than or equal to the next one. When you rotate a sorted array, you introduce exactly one break: the point where the largest value wraps around to the smallest. So a sorted-and-rotated array has at most one position where nums[i] > nums[i+1].

But there is one more detail. You also need to check the wrap-around from the last element back to the first. If the array [3, 4, 5, 1, 2] is valid, then nums[4] (which is 2) must be less than or equal to nums[0] (which is 3). This wrap-around comparison closes the loop and ensures the array truly forms a rotated sorted sequence.

The algorithm:

1. Walk through the array, comparing each pair nums[i] and nums[(i + 1) % n].
2. Count the number of positions where nums[i] > nums[(i + 1) % n].
3. If the count is at most 1, the array is sorted and rotated. Return true. Otherwise, return false.

The solution

def check(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

Let's walk through what each piece does.

The loop runs through every index from 0 to n - 1. For each index i, it compares nums[i] with nums[(i + 1) % n]. The modulo operation handles the wrap-around: when i is the last index, (i + 1) % n wraps back to 0, so we compare the last element with the first.

Each time we find a pair where the left element is strictly greater than the right, we increment count. This counts the number of "breaks" in sorted order.

Finally, we return count <= 1. A perfectly sorted array (no rotation) has zero breaks. A sorted array rotated by some positions has exactly one break. Anything with two or more breaks cannot be a sorted-and-rotated array.

Visual walkthrough

Let's trace through [3, 4, 5, 1, 2] step by step. We compare each adjacent pair (including the wrap-around from the last element back to the first) and count how many times the left side is greater than the right.

One break total. Since 1 <= 1, the array is sorted and rotated.

Complexity analysis

Time is O(n) because we make exactly one pass through the array, performing a constant-time comparison at each index. There is no nested loop or repeated work.

Space is O(1) because we only use a single integer counter. No additional data structures are needed regardless of input size.

The building blocks

1. Circular array traversal with modulo

The pattern of using (i + 1) % n to wrap around from the end of an array back to the beginning:

for i in range(n):
    next_i = (i + 1) % n
    compare(nums[i], nums[next_i])

This eliminates the need for special-case boundary logic. You will see this same technique in problems involving circular buffers, rotating arrays, and any scenario where the "next" element after the last one is the first.

2. Counting violations in a single pass

The pattern of scanning an array and counting how many positions violate a condition:

count = 0
for i in range(n):
    if violates_condition(nums[i], nums[(i + 1) % n]):
        count += 1
return count <= threshold

This is a general-purpose technique. You define what "violation" means, scan once, and check the count against a threshold. It works for verifying sorted order, checking monotonicity, validating rotation, and many other structural properties.

Edge cases

• Already sorted (no rotation): [1, 2, 3, 4] has zero breaks. 0 <= 1, so return true.
• Single element: [1] has zero breaks. Always true.
• Two elements: [2, 1] has one break (2 > 1), wrap-around is fine (1 < 2). Return true.
• All identical: [2, 2, 2, 2] has zero breaks. Always true.
• Not rotated-sorted: [3, 1, 2, 4] has two breaks (3 > 1 and 4 > 3 on wrap). Return false.
• Fully reversed: [4, 3, 2, 1] has three breaks. Return false.
• Duplicates at the rotation point: [2, 3, 3, 1, 2] has one break (3 > 1). The wrap-around 2 = 2 is fine. Return true.

From understanding to recall

The logic behind this problem is simple once you see it: count breaks, check if there is at most one. But simplicity does not mean you will remember the details under pressure. When you sit down in an interview, the question becomes: do you reach for % n instinctively, or do you fumble with off-by-one boundary checks?

Spaced repetition turns the % n wrap-around pattern into muscle memory. You practice writing the loop, the comparison, and the threshold check from scratch. After a few sessions, you do not need to think about whether the modulo goes on i or i + 1, or whether the threshold is < 1 or <= 1. It just comes out correctly.

This problem also reinforces a broader skill: reducing a problem to a single scan with a clean invariant. Many easy and medium problems follow this structure. The faster you can identify "what am I counting?" and "what is the threshold?", the faster you can solve them.

Related posts

• Search in Rotated Sorted Array - Binary search on a rotated array
• Find Minimum in Rotated Sorted Array - Finding the rotation point with binary search
• Rotate Array - The mechanics of array rotation

CodeBricks breaks Check if Array Is Sorted and Rotated into its circular traversal and violation-counting building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a rotation problem shows up in your interview, you do not think about it. You just write it.