Bitonic sequence

Question

A sequence is bitonic if it monotonically increases and then monotonically de- creases, or if it can be circularly shifted to monotonically increase and then monotonically decrease. For example the sequences (1, 4, 6, 8, 3, −2) , (9, 2, −4, −10, −5) , and (1, 2, 3, 4) are bitonic, but (1, 3, 12, 4, 2, 10) is not bitonic.

How can it be determined if given sequence is bitonic?

I have the following opinion. We can walk till n/2 where n is the length of the array and check if (a[i]<a[i+1] && (a[n-i-1]<a[n-1-(i+1)). Is it correct?

Answer 1

Walk through values, keeping track of whether the current is larger, equal to, or smaller than the previous. To be bitonic, it should grow, and then shrink. Once it starts shrinking, it can't grow again; every value must be smaller than the previous.

Answer 2

• Traverse the array forwards, wrapping around when you hit the end (code below)
• Count the total number of inflection points you find, if num_inflection_points==2 then your array is bitonic.
• The runtime of this should be O(n).

-

Here's a working example in c++:

bool is_bitonic(const vector<int>& v) {
  bool was_decreasing = v.back() > v.front();
  int num_inflections = 0;
  for (int i = 0; i < v.size() && num_inflections <= 2; i++) {
    bool is_decreasing = v[i] > v[(i+1)%v.size()];
    // Check if this element and next one are an inflection.
    if (was_decreasing != is_decreasing) {
      num_inflections++;
      was_decreasing = is_decreasing;
    }
  }
  return 2 == num_inflections;
}

• Notes, depending on your implementation:

Note 1: Here's the basic idea for traversing an array circularly:

for (int i = ip_index; i < array_length; i++) {
   int index = (i + 1) % array_length;  // wraps around to beginning
   // Retrieve the value with
   DoSomethingWithValue(array[index];)
}

Note 2: It might simplify the code to circularly loop length + 1 elemnts, which will guarantee you find both inflection points.

Note 3: Or, it might simplify the code if you always look for the first inflection point that goes increasing to decreasing (before searching for other inflection points). That way, your scan only has to take worry about finding exactly one other inflection point with the opposite flip.

Note 4: As for your example, you can't use N/2, because the inflection point doesn't necessarily occur at the midpoint of the array.

Answer 3

You can look for the peak, i.e. when a[i-1] < a[i] && a[i] > a[i+1], then a[i] is the local peak (taking care of wrap around with modulus operator).

In a bitonic sequence, there can only be one such peak. Once you found the peak, then you can walk downhill to the left (wrapping around as necessary, again using modulus) until you found an uphill. Then you go back to the peak, walk downhill to the right, until you found another uphill. Now, if a sequence is bitonic, then you will have covered the whole sequence by going downhill on both sides.

btw, do I misunderstood the question, or is your first example not bitonic?

Answer 4

There need to be exactly two (or, depending on how your definition deals with degeneracy, exactly 0) transitions between rising and falling. Don't forget to check the transition between a[n] and a[0].

Answer 5

A bitonic sequence:

 /\
/  \
    \/

Not a bitonic sequence:

 /\    
/  \  / (higher than start)
    \/

Obviously if the direction changes more than two times we cannot have a bitonic sequence.
If the direction changes less than two times, we must have a bitonic sequence.

If there are two changes in direction, we MAY have a bitonic sequence. Consider the two ascii images above. Clearly a sequence with two changes in direction will match one of the patterns (allowing for a reflection). Thus, we set the initial direction by comparing the first and last elements. Since these can be the same, we use the first element that is not equal to the last element.

Here is an implementation in Java:

public static Boolean bitonic(int[] array) {
    if (array == null) return false;
    if (array.length < 4) return true;
    Boolean dir;// false is decreasing, true is increasing
    int pos = 0, switches = 0;
    while (pos < array.length) {
        if (array[pos] != array[array.length - 1])
            break;
        pos++;
    }
    if (pos == array.length) return true;
    //pos here is the first element that differs from the last
    dir = array[pos] > array[array.length - 1];
    while (pos < array.length - 1 && switches <= 2) {
        if ((array[pos + 1] != array[pos]) &&
           ((array[pos + 1] <= array[pos]) == dir)) {
            dir ^= true;
            switches++;
        }
        pos++;
    }
    return switches <= 2;
}