# Check if Array Is Sorted and Rotated
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-array-is-sorted-and-rotated)
Canonical: https://scaleengineer.com/dsa/problems/check-if-array-is-sorted-and-rotated
**Data structures:** Array
**Companies:** [tcs](https://scaleengineer.com/companies/tcs), [SoundHound](https://scaleengineer.com/companies/soundhound)
---
## Problem
Given an array `nums`, return `true` _if the array was originally sorted in non-decreasing order, then rotated **some** number of positions (including zero)_. Otherwise, return `false`.

There may be **duplicates** in the original array.

**Note:** An array `A` rotated by `x` positions results in an array `B` of the same length such that `B[i] == A[(i+x) % A.length]` for every valid index `i`.

**Example 1:**

**Input:** nums = [3,4,5,1,2]
**Output:** true
**Explanation:** [1,2,3,4,5] is the original sorted array.
You can rotate the array by x = 3 positions to begin on the element of value 3: [3,4,5,1,2].

**Example 2:**

**Input:** nums = [2,1,3,4]
**Output:** false
**Explanation:** There is no sorted array once rotated that can make nums.

**Example 3:**

**Input:** nums = [1,2,3]
**Output:** true
**Explanation:** [1,2,3] is the original sorted array.
You can rotate the array by x = 0 positions (i.e. no rotation) to make nums.

**Constraints:**

* `1 <= nums.length <= 100`
* `1 <= nums[i] <= 100`

# Approaches
## Brute Force by Comparing with Rotated Sorted Array
This approach directly simulates the problem's definition. It first creates a sorted version of the input array. Then, it generates every possible rotation of this sorted array and compares each one with the original input array. If any of the rotated versions match the input array, the function returns true; otherwise, it returns false after checking all possibilities.
**Time:** O(N^2). Sorting the array takes O(N log N). The outer loop runs N times (for each rotation), and the inner loop for comparison also runs N times. This results in a complexity of O(N log N + N*N), which simplifies to O(N^2). · **Space:** O(N), where N is the number of elements in the array. This space is used to store the `sortedNums` array.
**Pros:** Easy to understand and implement as it directly follows the problem statement.; Guaranteed to be correct.
**Cons:** Highly inefficient with a time complexity of O(N^2), which is slow for larger arrays.; Requires O(N) extra space to store the sorted copy of the array.
### Explanation
The brute-force method is the most straightforward way to solve the problem. The core idea is to verify if the given array `nums` can be produced by rotating a sorted version of itself.

1.  **Sort a Copy:** First, we create a new array, `sortedNums`, which is a sorted version of the input `nums`. This gives us the 'original sorted array' mentioned in the problem description.
2.  **Generate and Compare Rotations:** We then systematically generate all `n` possible rotations of `sortedNums`. A rotation by `x` positions means the element at index `i` in the sorted array moves to index `(i + x) % n`. For each of these `n` rotations, we compare it element-by-element with the original `nums` array.
3.  **Return Result:** If we find any rotation of `sortedNums` that is identical to `nums`, we've confirmed that `nums` is a sorted and rotated array, so we return `true`. If we exhaust all `n` possible rotations without finding a match, it means `nums` cannot be formed this way, and we return `false`.

```java
import java.util.Arrays;

class Solution {
    public boolean check(int[] nums) {
        int n = nums.length;
        int[] sortedNums = new int[n];
        System.arraycopy(nums, 0, sortedNums, 0, n);
        Arrays.sort(sortedNums);

        // Try all n possible rotation offsets
        for (int x = 0; x < n; x++) {
            boolean match = true;
            // Check if this rotation matches the original array
            for (int i = 0; i < n; i++) {
                if (nums[i] != sortedNums[(i + x) % n]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- Create a copy of the input array `nums` and sort it. Let's call this `sortedNums`.
- Iterate through all possible rotation offsets, from `0` to `n-1`, where `n` is the length of the array.
- For each rotation offset `x`, check if the original array `nums` is equal to the `sortedNums` array rotated by `x`.
- To check for equality, iterate from `i = 0` to `n-1` and compare `nums[i]` with `sortedNums[(i + x) % n]`.
- If a match is found for any rotation `x`, return `true` immediately.
- If the loops complete without finding any matching rotation, return `false`.

## Find Minimum and Verify Sorted Order
This approach is based on the observation that if an array is sorted and rotated, the minimum element of the array acts as the pivot point where the rotation occurred. By finding this minimum element, we can identify the potential starting point of the original sorted sequence. We then verify if the array is sorted in non-decreasing order starting from this pivot and wrapping around.
**Time:** O(N). The first pass to find the minimum element takes O(N) time. The second pass to verify the sorted order also takes O(N) time. The total time complexity is O(N + N) = O(N). · **Space:** O(1), as it only uses a few variables to store indices and does not require any additional data structures proportional to the input size.
**Pros:** Efficient O(N) time complexity.; Optimal O(1) space complexity as it modifies nothing in place.
**Cons:** Requires two passes over the array, which is slightly less efficient than a single-pass solution.
### Explanation
A more optimized approach involves locating the pivot of the rotation. In a non-decreasingly sorted and rotated array, the smallest element is the pivot. For example, in `[3,4,5,1,2]`, the minimum element `1` is where the original sorted sequence `[1,2,3,4,5]` begins.

1.  **Find the Minimum:** The first step is to iterate through the array to find the index of the minimum element. Let's call this `minIndex`.
2.  **Verify Sorted Order:** Once we have the `minIndex`, we can conceptually 'un-rotate' the array. We then perform a second pass, starting from `minIndex`, to check if the elements are in non-decreasing order. This check involves comparing each element with its successor, wrapping around the end of the array to the beginning. The comparison looks like `nums[current_index] <= nums[next_index]`, where indices are calculated using the modulo operator to handle the wrap-around.
3.  **Return Result:** If all elements from the pivot point onwards are in sorted order, the function returns `true`. If at any point the order is broken, we can immediately return `false`.

```java
class Solution {
    public boolean check(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return true;
        }

        // 1. Find the index of the minimum element
        int minIndex = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }
        }

        // 2. Check if the array is sorted starting from minIndex
        for (int i = 0; i < n - 1; i++) {
            int currentIndex = (minIndex + i) % n;
            int nextIndex = (minIndex + i + 1) % n;
            if (nums[currentIndex] > nums[nextIndex]) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- Find the index of the minimum element in the array. Let this be `minIndex`. This requires a single pass through the array.
- If there are multiple minimum elements, any of their indices will work as the potential start of the sorted sequence.
- Once `minIndex` is found, treat the array as if it starts from this index and wraps around.
- Perform a second pass to verify if this 'un-rotated' sequence is sorted. Iterate from `i = 0` to `n-2`.
- In each step of the second pass, compare `nums[(minIndex + i) % n]` with `nums[(minIndex + i + 1) % n]`.
- If you find any pair where `nums[(minIndex + i) % n] > nums[(minIndex + i + 1) % n]`, the array is not correctly sorted and rotated, so return `false`.
- If the second pass completes without finding any such pair, the array is valid. Return `true`.

## Single Pass by Counting Breaks
This is the most efficient approach. It leverages a key insight: a non-decreasingly sorted array that has been rotated will have at most one point where an element is greater than the element that follows it. This includes the 'wrap-around' case where the last element is compared to the first. By making a single pass through the array and counting these 'breaks' or 'inversions', we can solve the problem.
**Time:** O(N). The algorithm iterates through the array exactly once, performing a constant number of operations at each step. · **Space:** O(1). It only requires a single integer variable (`breaks`) for counting, resulting in constant extra space.
**Pros:** Most efficient solution with O(N) time complexity in a single pass.; Optimal O(1) space complexity.; The code is very concise and elegant.
**Cons:** The logic, while concise, might be slightly less intuitive to grasp initially compared to more direct methods.
### Explanation
The optimal solution is elegant and relies on a simple observation. When a sorted array is rotated, it creates at most one 'discontinuity' or 'break point' where `nums[i] > nums[i+1]`. 

- A perfectly sorted array like `[1, 2, 3, 4]` has zero such breaks. If we consider the wrap-around from last to first element (`4 > 1`), there is one break.
- A rotated array like `[3, 4, 1, 2]` has one break (`4 > 1`).
- An unsorted array like `[2, 1, 3, 4]` has two breaks (`2 > 1` and `4 > 2` when wrapping around).

Therefore, an array is a sorted and rotated version of another if and only if the number of these breaks is less than or equal to one. We can simply iterate through the array once, count the number of breaks, and return the result.

The check `nums[i] > nums[(i + 1) % n]` cleverly handles both internal breaks and the wrap-around break between the last and first elements in a single loop.

```java
class Solution {
    public boolean check(int[] nums) {
        int n = nums.length;
        int breaks = 0;

        for (int i = 0; i < n; i++) {
            // Compare current element with the next, wrapping around using modulo
            if (nums[i] > nums[(i + 1) % n]) {
                breaks++;
            }
        }

        // If there is 0 or 1 break, the array is sorted and rotated.
        return breaks <= 1;
    }
}
```
### Algorithm
- Initialize a counter variable, `breaks`, to zero.
- Iterate through the array from `i = 0` to `n-1`.
- In each iteration, compare the current element `nums[i]` with the next element `nums[(i + 1) % n]`. The modulo operator `% n` is crucial here as it handles the wrap-around comparison between the last and the first element.
- If `nums[i] > nums[(i + 1) % n]`, it signifies a 'break' in the non-decreasing order. Increment the `breaks` counter.
- After the loop finishes, check the value of `breaks`.
- If `breaks` is 0 (array is fully sorted with no breaks) or 1 (array is rotated once), the condition is satisfied. Return `true`.
- If `breaks` is greater than 1, it means there are multiple points of disorder, so the array could not have been formed from a single sorted sequence. Return `false`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  bool check(vector<int> &nums) {
    int cnt = 0;
    for (int i = 0, n = nums.size(); i < n; ++i) {
      cnt += nums[i] > (nums[(i + 1) % n]);
    }
    return cnt <= 1;
  }
};

```

### Python

```python
class Solution:
    def check(self, nums: List[int]) -> bool: return sum(
        nums[i - 1] > v for i, v in enumerate(nums)) <= 1

```