Check if Array Is Sorted and Rotated on LeetCode

Question

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.

Answer 1

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());

Answer 2

You have a general misunderstanding of how ranges are denoted by iterators. C++ uses the convetion of half open intervals [first,last), ie first is included while last is not included.

When the range is 3 4 5 1 2 3 then std::sorted_until returns an iterator to 1 (not to 5). The second half is checked via std::is_sorted(pivot, nums.end()) (no +1 !).

---

In the example in main the pivot element has value 1, it is the second element.

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';

It prints true, because you are checking whether a sorted range is sorted.

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

This prints true, because 1 3 4 is sorted.

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

Apart from the 1 missing element mentioned above, the else branch in the function is equivalent to what main does. true && true is true hence the function returns true.

---

The function should return false for 2 1 3 4 because when rotated the vector is 1 3 4 2 is not sorted. However thats not what you function checks.

Your function checks if the input consists of 2 subarrays that are sorted. It does not check if the whole array is sorted.

To fix your code you should test if the whole array is sorted not just the two subarrays separately.

Answer 3

Instead of checking for multiple conditions simultaneously I think this approach is simpler, please check it out too:

Method:

• Iterating over each element in the array, you can increment a var integer each time current element is greater than the next element.

• To include the additional condition of boundary elements, use modulo operator to traverse array as a circular array.

  (taking n = array.size())

      for (int i = 0; i < n; i++)
                   {
                     if (array[i] > array[(i+1) % n])
                         count++;
                   }
                return (count <= 1);