Method 1 - Naive

Now the naive approach can be:

For each possible position in the array, we rotate the array to the left - in a way undoing the rotation to the right given in the original.
Validate if the array is sorted in any of the rotations. If it is, then the array was rotated and sorted; otherwise, it was not.

Consider the array nums = [3, 4, 5, 1, 2].

Rotation 0 (no rotation): [3, 4, 5, 1, 2] (not sorted)
Rotation 1: [4, 5, 1, 2, 3] (not sorted)
Rotation 2: [5, 1, 2, 3, 4] (not sorted)
Rotation 3: [1, 2, 3, 4, 5] (sorted, return true)

Pseudocode

Here is the pseudocode:

function check(nums):
    n = length(nums)
    for x from 0 to n-1:
        rotated = rotate(nums, x)
        if isArraySorted(rotated):
            return true

Related Tags