# Solution For Check If Array Is Sorted And Rotated

Problem Statement:
Given an integer array nums, return true if the array is monotonic and its rotated by some indices, otherwise return false.
An array is monotonic if it’s either increasing or decreasing.

Example 1:
Input: nums = [3,4,5,1,2] Output: true
Explanation: The array can be rotated 1 time to the right, and become [2,3,4,5,1]. This is a sorted array.

Example 2:
Input: nums = [2,1,3,4] Output: false
Explanation: There’s no way to rotate the array to make it sorted.

Approach:
To solve this problem, we can check whether the array can be split into two parts that are both sorted in non-descending order and one part is shifted to the left of another part. If we can find such a split point, then the array is a sorted and rotated array.

To find the split point, we need to traverse the array and compare each element with its next element. If a smaller element is found, then this element is the split point. For example, if the array is [5, 6, 0, 1, 2, 3, 4], then the split point is 0.

Then we need to check whether both parts are sorted. To do this, we can compare the last element of the first part with the first element of the second part. If the last element of the first part is greater than the first element of the second part, then the array is not sorted and rotated.

Implementation:

Here is a possible implementation of the solution:

`class Solution { public: bool check(vector<int>& nums) { int n = nums.size(); int split = -1; for (int i = 0; i < n; i++) { if (nums[i] > nums[(i + 1) % n]) { split = i; break; } } if (split == -1) return true; for (int i = split + 1; i < n; i++) { if (nums[i] < nums[i - 1]) return false; } return nums[n - 1] <= nums[0]; } };`

First, we initialize a variable `split` with -1. This variable will be used to store the index of the split point.

Next, we traverse the array using a `for` loop. Inside the loop, we compare each element with its next element. If we find that an element is greater than its next element, then we have found the split point, so we store its index in the `split` variable and break out of the loop.

Then we check whether the `split` variable has been updated or not. If the variable is still -1, it means that there is no split point, and the array is already sorted. In this case, we return true.

Otherwise, we traverse the second part of the array using another `for` loop. Inside the loop, we compare each element with its previous element. If we find that an element is smaller than its previous element, then the array is not sorted and rotated, so we return false.

Finally, we check whether the last element of the first part is less than or equal to the first element of the second part. If this condition is satisfied, then the array is sorted and rotated, so we return true. Otherwise, we return false.

Time Complexity:
The time complexity of the solution is O(n), where n is the size of the input array. This is because we need to traverse the array at most twice, which takes O(n) time in total.

Space Complexity:
The space complexity of the solution is O(1), because we only use a few variables to store the split point and the size of the input array.

## Step by Step Implementation For Check If Array Is Sorted And Rotated

```public boolean isSortedAndRotated(int[] array) {
// check if the array is null or empty
if(array == null || array.length == 0) {
return false;
}

// find the minimum element in the array
int min = array[0];
for(int i = 1; i < array.length; i++) {
if(array[i] < min) {
min = array[i];
}
}

// check if the array is sorted
for(int i = 1; i < array.length; i++) {
if(array[i] < array[i-1]) {
return false;
}
}

// check if the array is rotated
int index = -1;
for(int i = 0; i < array.length; i++) {
if(array[i] == min) {
index = i;
break;
}
}

if(index == -1) {
return false;
}

for(int i = 0; i < array.length - 1; i++) {
if(i + index >= array.length) {
if(array[i] > array[i+index-array.length]) {
return false;
}
} else {
if(array[i] > array[i+index]) {
return false;
}
}
}

return true;
}```
```def checkIfSortedAndRotated(arr, n):

# We need to check if array is sorted and then rotated
# We can check if array is sorted by comparing the first
# and last element of the array
if (arr[0] < arr[n - 1]):
return True

# We need to find the point of rotation
# We can find the point of rotation by comparing the
# elements of the array
for i in range(0, n - 1):
if (arr[i] > arr[i + 1]):
return True

return False```
```function isSortedAndRotated(arr) {
// check if the array is empty
if (arr.length === 0) {
return false;
}
// get the first element of the array
let first = arr[0];
// loop through the array starting at the second element
for (let i = 1; i < arr.length; i++) {
// if the current element is less than the first element,
// then the array is sorted and rotated
if (arr[i] < first) {
return true;
}
}
// if we get through the loop and no elements were less than
// the first element, then the array is sorted but not rotated
return false;
}```
```bool isRotatedAndSorted(int arr[], int n)
{
// Find the minimum element in array
int min = arr[0], min_index;
for (int i = 0; i < n; i++)
{
if (min > arr[i])
{
min = arr[i];
min_index = i;
}
}

// Check if all elements are equal
if (min_index == 0)
return true;

// Check if elements from 1 to min_index - 1 are sorted
for (int i = 1; i < min_index; i++)
if (arr[i] < arr[i-1])
return false;

// Check if elements from min_index to n - 1 are sorted
for (int i = min_index+1; i < n; i++)
if (arr[i] < arr[i-1])
return false;

return true;
}```
```public bool IsSortedAndRotated(int[] array)
{
// This is the case when the array is not rotated at all
if(array[0] < array[array.Length - 1])
{
return IsSorted(array);
}

int minElementIndex = FindMinElementIndex(array);

// This is the case when the array is sorted and rotated by one element
if(minElementIndex == 0)
{
return true;
}

// This is the case when the array is sorted and rotated by more than one element
if(IsSorted(array, 0, minElementIndex - 1) && IsSorted(array, minElementIndex, array.Length - 1))
{
return true;
}

return false;
}

private bool IsSorted(int[] array)
{
for(int i = 0; i < array.Length - 1; i++)
{
if(array[i] > array[i + 1])
{
return false;
}
}

return true;
}

private bool IsSorted(int[] array, int start, int end)
{
for(int i = start; i < end; i++)
{
if(array[i] > array[i + 1])
{
return false;
}
}

return true;
}

private int FindMinElementIndex(int[] array)
{
int minElement = array[0];
int minElementIndex = 0;

for(int i = 1; i < array.Length; i++)
{
if(array[i] < minElement)
{
minElement = array[i];
minElementIndex = i;
}
}

return minElementIndex;
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]