Check if Array Is Sorted and Rotated on LeetCode

I am trying to solve LeetCode problem 1752. Check if Array Is Sorted and Rotated:

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 A[i] == B[(i+x) % A.length], where % is the modulo operation.

I'm stuck at this question. I was trying to solve it with std::is_sorted and std::is_sorted_until, but I get wrong results.

Here's my code:

class Solution
{
public:
    bool check(const std::vector<int>& nums)
    {
        // If the array is sorted without rotation.
        if (const auto pivot = std::is_sorted_until(nums.begin(), nums.end());
            pivot == nums.end())
        {
            return true;
        }
        // If there is a rotation, pivot will be our
        // point of rotation.
        else
        {
            // Check both halves.
            /**
             *     pivot
             *   ~~~~| 
             *   3 4 5 1 2 3
             *   ~~~~~       -> first half
             *         ~~~~~ -> second half
            */
            return std::is_sorted(nums.begin(), pivot) &&
                   std::is_sorted(pivot + 1, nums.end());
        }
    }
};

It fails on input {2, 1, 3, 4}. Why is that?

The pivot is the second item and it is not sorted but std::is_sorted(nums.begin(), pivot) returns true as I tested:

int main()
{
    Solution   sol;
    std::vector v{2, 1, 3, 4};

    const auto pivot = std::is_sorted_until(v.begin(), v.end());
    std::cout << std::distance(v.begin(), pivot) << '\n'; // The index of the pivot.

    // Why it prints true???
    std::cout << std::boolalpha << std::is_sorted(v.begin(), pivot) << '\n';

    // Prints true?
    std::cout << std::boolalpha << std::is_sorted(pivot, v.end()) << '\n';

    // Should print false but it prints true.
    std::cout << std::boolalpha << sol.check(v) << '\n';
}

I have tried modifying the iterator inputs, especially the end iterators.

There are two issues:

1. pivot will point to the first value that is not sorted, so it references the first value that belongs to the second partition of your vector. Therefor the test should not be std::is_sorted(pivot + 1, nums.end()), but std::is_sorted(pivot, nums.end())

2. Even if the two partitions are sorted, that doesn't imply yet that it is the rotation of a sorted sequence. The example proves this: given {2, 1, 3, 4}, {2} is sorted, and also {1, 3, 4} is sorted, but the total is not a rotation of a sorted sequence. That is because the partitions have a sequence that overlaps. You need a third condition, which says that the last value in the vector is not greater than the first.

In fact, you can omit the check on the first partition, because your earlier call of is_sorted_until already asserted that this partition is sorted.

So the final return statement should be:

            return nums.back() <= nums[0] &&
                   std::is_sorted(pivot, nums.end());