Check if Array Is Sorted and Rotated

class Solution {
public:
    bool checkArrayRotation(vector<int>& elements) {
        int size = elements.size();
        if (size <= 1) return true;

        int kinks = 0;

        // Iterate and find if there is more than one descending order breach
        for (int i = 1; i < size; ++i) {
            if (elements[i] < elements[i - 1]) {
                ++kinks;
                if (kinks > 1) return false;
            }
        }

        // Check connection between end and beginning due to cyclic nature
        if (elements[0] < elements[size - 1]) {
            ++kinks;
        }

        return kinks <= 1;
    }
};

You need to determine if a given array has been sorted in non-decreasing order and then potentially rotated. To solve this in C++, the method checkArrayRotation within the Solution class is employed.

The function takes a vector of integers, elements, as its input and returns a boolean indicating if the array is sorted and rotated. Here is an overview of how the solution works:

• First, calculate the size of the vector. If the size is 1 or less, the function immediately returns true as a single element or an empty array is inherently sorted and rotated.

• Initialize a counter, kinks, to count breaches in the sorted order. This tracks points where the order moves from a higher element to a lower one.

• Iterate through the elements of the vector:

  • For each pair of consecutive elements, if a decrease is found (i.e., the current element is less than the previous one), increment the kinks counter.
  • Break early if kinks exceeds 1 since more than one kink means the array couldn’t have been just rotated—it must be unordered in some way.

• After completing the traversal of inside elements, also check the connection between the last and the first element owing to the cyclic nature of a rotation. Increment kinks if the first element is less than the last element.

• Finally, the array is considered to have been sorted and then rotated if there is at most one kink, hence return whether kinks is less than or equal to 1.

This function effectively checks both the sorted nature and possible cyclic rotation by examining the transitions between consecutive elements and handling the cyclic property at the beginning and end of the array.

class Solution {

    public boolean validateRotation(int[] elements) {
        int size = elements.length;
        if (size <= 1) return true;

        int incorrectOrder = 0;

        // Counting inversions for cyclically sorted array
        for (int index = 1; index < size; ++index) {
            if (elements[index] < elements[index - 1]) {
                incorrectOrder++;
                if (incorrectOrder > 1) return false;
            }
        }

        // Check rotational order between last and first in the array
        if (elements[0] < elements[size - 1]) {
            ++incorrectOrder;
        }

        return incorrectOrder <= 1;
    }
}

The provided Java implementation checks if a given array can be considered sorted and rotated using a method named validateRotation. This method efficiently determines if the elements of the array form a cycle that could be seen as a sorted array that has been rotated. The key steps and logic employed in the solution are outlined below:

• Start by obtaining the length of the array. If the array contains one or no elements, it immediately returns true, as such arrays are trivially sorted and considered rotated.
• Define a counter incorrectOrder to keep track of the number of violations of the sorted order.
• Iterate over the array and compare each element with the previous one to check for order violations. Specifically, if the current element is smaller than the previous element, increment the incorrectOrder counter.
• More than one violation during this sequential check means the array cannot be just rotated, it must also have an out-of-order element, so return false if incorrectOrder exceeds one.
• Additionally, check the boundary condition between the last and the first element of the array to allow for array rotation. If the first element is less than the last element, increment the incorrectOrder.
• Finally, evaluate the total violations observed (incorrectOrder) which should not exceed one for the array to be considered sorted and then rotated.

This method efficiently decides the condition with a single pass through the array, checking for a maximum of one disorderly pivot, thus ensuring minimum computational overhead. The solution leverages the properties of cyclic order and array boundaries to make an accurate determination using linear time complexity.

class Solution:
    def isValidRotation(self, values: List[int]) -> bool:
        length = len(values)
        if length <= 1:
            return True

        num_inversions = 0

        for i in range(1, length):
            if values[i] < values[i - 1]:
                num_inversions += 1
                if num_inversions > 1:
                    return False

        if values[0] < values[length - 1]:
            num_inversions += 1

        return num_inversions <= 1

The provided Python code defines a method within a Solution class to determine whether an array is sorted and could have been rotated to make it appear unsorted. Here's a breakdown of how the solution works:

• Firstly, the method isValidRotation receives a list of integers, values.
• The method checks the array's length. If the array contains one or no elements, it is automatically considered valid since a single element or empty list is trivially both sorted and rotated.
• The method then initializes a counter num_inversions to track where the current element is smaller than the previous one, which could indicate a 'rotation point' or an irregularity in a sorted list.
• A loop iterates through the array, comparing each current element to its predecessor. If the current element is smaller, num_inversions increments. If more than one such inversion is found, the array cannot be a sorted list rotated at most once, therefore, the method returns False.
• After iterating through the array, the method finally checks if the first element is smaller than the last. If so, this is a valid condition for a rotation of a sorted list, the inversion count gets incremented.
• If the total inversions found through the array are less than or equal to one, the function returns True, indicating the list could indeed be a sorted array that has been rotated.

The algorithm effectively captures the essence of checking if a rotation of a sorted array could yield the given sequence, ensuring that these rotations don't disrupt the order more than once around the list. This approach effectively uses comparison and counter increment operations, achieving a time complexity of O(n), where n is the number of elements in the array.