How to check if an int array is a circularly sorted array?

Question

I have an integer array, say {1, 3, 4, 7, -9, 0}. This array is circularly sorted, while the array {2, 4, 9 , 3} is not circularly sorted.

An array is circularly sorted if its elements are sorted except for a rotation.

For example:

4 5 6 7 1 2 3

The elements here, 1 2 3 4 5 6 7, are "in order", but they are rotated to the left by three. So if we rotate to the right by 3 we get 1 2 3 4 5 6 7 which is a sorted array.

Given an array, how can you check whether the array is a circularly sorted?

Answer 1

You can loop through the array and check that all values are increasing. And as soon as you hit the first value that is not increasing, check that it and all of the following values are increasing AND less than or equal to the first element in the array.

Edit:

I feel that people are discounting Daniel's solution because they don't understand it or think it is broken. This is sad because I think his solution is brilliant.

def is_circular_sorted(arr):
    count = 0
    length = len(arr)
    for i in range(length):
        if arr[i] > arr[(i+1) % len(arr)]:
            count += 1
    return count <= 1

In [4]: is_circular_sorted([1, 2, 3, 4])
Out[4]: True

In [5]: is_circular_sorted([1, 1, 1, 1])
Out[5]: True

In [6]: is_circular_sorted([1, 3, 4, 7, -9])
Out[6]: True

In [7]: is_circular_sorted([1, 3, 4, 2])
Out[7]: False

For a little bit of explanation. To check if a list is circular-sorted, my original answer said you needed to check there was one or less "break" from being completely sorted AND all of the numbers after the "break" were less than the first number in the array.

However as Daniel's answer shows, you don't need to check ALL numbers after the "break", only the last number (which also happens to be the biggest/maximum number after the break because they are sorted).

There should always be one break, unless the list is filled with the same numbers in which case there would be no breaks and count would be 0.

Answer 2

In case some of the users wonder how the implementation looks like.

public boolean isCircularSorted(int[] array)
{
    int size = array.length;
    int count = 0;

    for(int x=0; x<size; x++)
        if(array[x] > array[(x+1)%size])
            count ++;
    return (count <= 1);
}

This was also mentioned by user Daniel.

Answer 3

As @Daniel said, using value[i] > value[(i+1)%length], if it true we count up 1, if the count at the end equals to 0 or 1, the original array is circularly sorted array! I think it is a good way!!