Check whether exists index k such that elements of array A[] moved clockwise make a reverse bitonic array

Viewed 62

Check whether exists index 0 <= k < n - 2 such that elements of array A[] moved clockwise by k indexes make a reverse bitonic array. My approach to do it in O(n) time complexity:

bool is_antibitonicable(int A[], int n) {
    // returns if there is such index k that 
    // after moving clockwise k elements of array
    // A[], that array is reverse bitonic
    // - strictly decreasing then strictly
    // increasing
    if (n < 3)
        return false;
    // if is_increasing[i] == 1 means this part of A[] is increasing,
    // == 0 means that part of A[] is decreasing, == -1 default
    int is_increasing[3] = { -1, -1, -1 };
    for (int i = 0, j; i < n - 1;) {
        if (A[i] < A[i + 1]) { // if A[] is increasing
            j = 0;
            while (j < 3 && is_increasing[j] != -1)
                j++;
            if (j == 3)
                return false;
            is_increasing[j] = 1;
            while (i < n - 1 && A[i] < A[i + 1])
                i++;
        }
        else if (A[i] > A[i + 1]) { // check if decreasing
            j = 0;
            while (j < 3 && is_increasing[j] != -1)
                j++;
            if (j == 3)
                return false;
            is_increasing[j] = 0;
            while (i < n - 1 && A[i] > A[i + 1])
                i++;
        }
        else // sequence of A[] is neither increasing nor decreasing
            return false;
    }
    // if A[] is only increasing/decreasing
    if (is_increasing[1] == is_increasing[2])
        return false;
    // if A[] is increasing->decreasing->increasing check if increasing
    // parts can be merged into one increasing sequence
    if (is_increasing[0] == 1 && is_increasing[1] == 0 && is_increasing[2] == 1)
        return (A[0] > A[n - 1]);
    // decreasing->increasing->decreasing
    if (is_increasing[0] == 0 && is_increasing[1] == 1 && is_increasing[2] == 0)
        return (A[0] < A[n - 1]);
    return true; // increasing -> decreasing or opposite
}

I'd be very glad if someone could look at my solution and comment whether it seems correct or how to do it better, any feedback will be appreciated.

1 Answers

Your solution doesn't look bad, but it does incorrectly return false // if A[] is only increasing/decreasing. Such a sequence can always be turned into a first decreasing and then increasing one by rotating by one in the right (appropriate) direction.

Related