Check if Array Is Sorted and Rotated

Check if Array Is Sorted and Rotated

What is this problem about?

The "Check if Array Is Sorted and Rotated interview question" asks you to determine if a given array was originally sorted in non-decreasing order and then rotated some number of positions. For example, [3, 4, 5, 1, 2] is a sorted and rotated version of [1, 2, 3, 4, 5].

Why is this asked in interviews?

This "Check if Array Is Sorted and Rotated coding problem" is a popular question for companies like Google and Goldman Sachs. It tests a candidate's ability to identify a global property (sortedness) within a modified sequence. It evaluates "Array interview pattern" logic—specifically, how to count "descending steps" in a circular array.

Algorithmic pattern used

The most efficient solution uses Linear Scan with Circular Continuity.

1. Count Disruptions: In a sorted array, arr[i] <= arr[i+1] for all i. In a sorted and rotated array, there can be at most one "drop" where arr[i] > arr[i+1].
2. Circular Check: You must also check the transition from the last element back to the first (arr[n-1] vs arr[0]).
3. Condition: If the total number of times arr[i] > arr[(i+1)%n] is 1 or 0, then the array is a rotated sorted array.

Example explanation

Array: [3, 4, 5, 1, 2]

1. 3 vs 4: OK.
2. 4 vs 5: OK.
3. 5 vs 1: Drop! (Count = 1).
4. 1 vs 2: OK.
5. 2 vs 3: OK. Total drops = 1. Result: True. Array: [2, 1, 3, 4]
6. 2 vs 1: Drop! (Count = 1).
7. 1 vs 3: OK.
8. 3 vs 4: OK.
9. 4 vs 2: Drop! (Count = 2). Total drops = 2. Result: False.

Common mistakes candidates make

• Ignoring the Wrap-around: Forgetting to compare the last element with the first element. This is crucial for detecting rotations.
• Assuming Unique Elements: The logic must handle duplicates (e.g., [1, 1, 1]). The condition is arr[i] > arr[i+1], not !=.
• Complexity: Attempting to actually "un-rotate" the array, which is unnecessary and complicated.

Interview preparation tip

Circular array problems are very common. Always think about using the modulo operator % or comparing the "tail" to the "head." This simple $O(N)$ pass is much better than trying to find the pivot using binary search.