Check if an Array is Sorted and Rotated

Title: Check if an Array is Sorted and Rotated

In this guide, you’ll learn how to check whether an array could be the result of taking a sorted array and rotating it some number of times. It’s a popular array-pattern interview question because the brute-force solution is easy to reach for, but the elegant single-pass solution says a lot about how well you understand sorted order.

Understanding the Problem

An array is sorted and rotated if you can take some ascending array like [1, 2, 3, 4, 5], pick a pivot, and rotate it so the elements wrap around. For example, [3, 4, 5, 1, 2] is [1, 2, 3, 4, 5] rotated two positions to the left. An array that is already sorted counts too, since that’s a rotation of zero.

The naive approach checks every possible rotation and tests whether each one is sorted, which costs O(n^2) time. The key insight that unlocks an O(n) solution is that a sorted-and-rotated array has at most one place where an element is followed by a smaller one, once you treat the array as circular and let the last element wrap back to the first.

Approach

The algorithm below counts how many times the array drops as you move from one element to the next, including the wrap-around pair from the last element back to the first. Follow these steps:

1. Read the array nums and store its length in n.
2. Initialize a counter breakCount to 0.
3. Loop i from 0 to n - 1.
4. For each i, compute the circular next index as (i + 1) % n so that when i is n - 1, the comparison wraps back to index 0.
5. If nums[i] is strictly greater than nums[next], increment breakCount; this marks a descent, which is where a rotation point would sit.
6. After the loop finishes, if breakCount is 0 the array is already sorted in ascending order with zero rotations.
7. If breakCount is exactly 1, the array is a sorted array rotated at that single descent; if it is 2 or more, return false because no single rotation of a sorted array can produce more than one descent.

Java Program

Here’s a complete, compilable program that implements the circular break-counting approach described above.

public class CheckSortedRotatedArray {

    public static boolean isSortedAndRotated(int[] nums) {
        int n = nums.length;
        int breakCount = 0;

        for (int i = 0; i < n; i++) {
            int next = (i + 1) % n;
            if (nums[i] > nums[next]) {
                breakCount++;
            }
        }

        return breakCount <= 1;
    }

    public static void main(String[] args) {
        int[] nums = {3, 4, 5, 1, 2};
        System.out.println(isSortedAndRotated(nums));
    }
}

Explanation of the Program

The method isSortedAndRotated does all the work in a single pass over the array. Here’s what each part is doing:

• n stores the array length once so it isn’t recomputed inside the loop.
• breakCount starts at 0 and tallies how many adjacent pairs violate ascending order.
• next = (i + 1) % n is the trick that makes the comparison circular; without the modulo, the pair (nums[n - 1], nums[0]) would never be checked.
• The condition nums[i] > nums[next] uses strict greater-than, so equal neighbors such as repeated values never count as a descent.
• Every descent found increments breakCount by one.
• The final return breakCount <= 1 accepts both the zero-rotation case and the single-rotation case, and rejects everything else.

Step-by-Step Trace

Trace the algorithm on nums = {4, 5, 6, 7, 0, 1, 2}, which should return true because it's {0, 1, 2, 4, 5, 6, 7} rotated so the run starting at 0 wraps to the front.

At the end of each iteration, breakCount holds the exact number of descents found among all circular adjacent pairs examined so far, and the array can only be sorted-and-rotated if that count never climbs past 1.

Examples

Example 1: A Rotated Sorted Array

The array {3, 4, 5, 1, 2} is {1, 2, 3, 4, 5} rotated two steps, so the method should return true.

int[] nums = {3, 4, 5, 1, 2};
System.out.println(isSortedAndRotated(nums));
// Output: true

Example 2: Not a Rotation of a Sorted Array

The array {2, 1, 3, 4} has two descents, one from 2 to 1 and another from 4 back to 2 at the wrap, so it can't come from rotating a sorted array.

int[] nums = {2, 1, 3, 4};
System.out.println(isSortedAndRotated(nums));
// Output: false

Example 3: All Elements Equal

An array like {3, 3, 3, 3} has no strict descents anywhere, including at the wrap-around pair, so it counts as sorted with zero rotations.

int[] nums = {3, 3, 3, 3};
System.out.println(isSortedAndRotated(nums));
// Output: true

Common Mistakes to Avoid

These are the mistakes that most often trip up a first attempt at this problem.

• Skipping the wrap-around comparison - comparing only nums[i] to nums[i + 1] for i from 0 to n - 2 never checks the pair (nums[n - 1], nums[0]), so a valid rotation like {3, 4, 5, 1, 2} can be misjudged. Always compare nums[i] to nums[(i + 1) % n] for every index, including the last one.
• Rejecting any descent instead of allowing exactly one - returning false the moment a single nums[i] > nums[i + 1] is found treats the one legitimate rotation point as an error. Count the descents and only return false once the count exceeds 1.
• Using >= instead of > when counting descents - this flags neighboring duplicate values, such as the repeated 2s in {1, 2, 2, 3}, as extra descents and wrongly rejects a valid array. Count a break only when the comparison is strictly nums[i] > nums[next].
• Confusing sorted-and-rotated with reverse-sorted-and-rotated - some learners also accept descending rotations such as {3, 2, 1, 5, 4}. Unless the problem explicitly allows that variant, only ascending-then-rotated arrays should return true.

Edge Cases to Test

Walk through these inputs before you consider the solution finished.

• Empty array
• Single-element array
• Already sorted array (zero rotations)
• All identical elements
• Rotation point at the last index
• Rotation point at index 1
• Array with exactly two descents
• Integer.MIN_VALUE and Integer.MAX_VALUE present

Additional Considerations

The circular break-counting approach runs in O(n) time since it visits every index exactly once, and it uses O(1) extra space because only the counter breakCount and the loop index are needed.

Compare that to the brute-force approach of rotating the array n times and checking whether each rotation is sorted, which costs O(n^2) time, or sorting a copy and comparing against every rotation, which costs at least O(n log n). The break-counting trick avoids both.

This same circular-descent-counting idea shows up in several related array problems, such as finding the minimum in a rotated sorted array or detecting the rotation count itself, so it's worth remembering beyond this one question.

Interview Follow-up Questions

Once you've nailed the base case, expect an interviewer to push further with questions like these.

• What if duplicate values are allowed throughout the array? - the strict > comparison already tolerates equal neighbors, so the same single-pass count works without any code change.
• What if you also need to report the index where the rotation occurred? - track the index where nums[i] > nums[next] is true instead of only counting it; that index plus one marks the start of the sorted run.
• What if the array arrives as a stream of unknown length instead of all at once? - keep the first value seen, the previous value, and a running breakCount, updating on each new element and only checking the wrap-around pair once the stream ends.
• What if you need to answer this question for many sub-ranges of the same large array? - precompute the positions of every descent once in O(n), then answer each range query by counting how many precomputed descent positions fall inside it using binary search.
• What if you must verify this using only read-only access to the array and no extra data structures? - the circular break-counting approach already satisfies that constraint; confirm no sorting, copying, or auxiliary array sneaks into the implementation.

Conclusion

Checking whether an array is sorted and rotated comes down to counting circular descents: zero means it's already sorted, exactly one means it's a valid rotation, and anything more rules it out. Once you see that pattern, the O(n) solution becomes the obvious one instead of the clever one.

Try adapting the same isSortedAndRotated method to also return the rotation count, or to work on a descending array instead of an ascending one. You can learn more about array-based interview problems in the Arrays category on the blog.