Check If Array Is Sorted And Rotated - Leetcode Solution

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.

1