Check if Array Is Sorted and Rotated

summary

• Given an array of integers, return true if the array was originally sorted in non-decreasing order, then rotated some number of positions, otherwise return false.

approach

• The approach used is to find the minimum element in the array and the index of the minimum element
• Then, check if the array can be rotated such that the minimum element becomes the first element
• If it can, return true, otherwise return false.

complexity

• O(n) where n is the number of elements in the array

explain

• The solution code first finds the minimum element in the array and its index
• Then, it checks if the array can be rotated such that the minimum element becomes the first element
• If it can, it means the array was originally sorted in non-decreasing order and then rotated some number of positions
• If it cannot, it means the array was not rotated and therefore the array was not originally sorted in non-decreasing order.

Solution Code:

class Solution {
public:
    bool check(vector& nums) {
        int N = nums.size();
        int minIdx = 0;
        int minValue = 101;
        for(int i = 0; i 
            if(minValue> nums[i]){
                minIdx = i;
                minValue = nums[i];
            }
        }
        int idx = N - 1;
        while(idx >= 0 && minIdx != N-1 && nums[minIdx] == nums[idx]){
            idx--;
        }
        if(idx != N-1){
            minIdx = idx + 1;
        }
        int beforeVal = nums[minIdx];
        minIdx = (minIdx + 1) %N;
        int n = N;
        n--;
        while(n--){
            if(beforeVal > nums[minIdx]){
                return false;
            }
            beforeVal = nums[minIdx];
            minIdx = (minIdx + 1) %N;
        }
        return true;
    }
};