Bitonic Sequence

A bitonic sequence is a sequence of numbers that first monotonically increases, then monotonically decreases. It has one peak where the transition occurs from increasing to decreasing.

For example: [1, 2, 5, 4, 3] is a bitonic sequence with peak 5.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
boolean isBitonic(int[] arr) {
  int n = arr.length;
  int i = 0;

  // Find max element
  while (i+1 < n && arr[i] < arr[i+1])  
    i++;

  // After peak, remaining elements must be decreasing   
  while (i+1 < n && arr[i] > arr[i+1]) 
    i++;

  // Sequence is bitonic if we reached the end  
  return i == n-1;
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
bool isBitonic(vector<int> arr) {
  int n = arr.size();
  int i = 0;

  while (i+1 < n && arr[i] < arr[i+1])
    i++;
  
  while (i+1 < n && arr[i] > arr[i+1])
    i++;

  return (i == n-1);
}

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def is_bitonic(arr):
  n = len(arr)
  i = 0
  
  while i+1 < n and arr[i] < arr[i+1]:
    i += 1

  while i+1 < n and arr[i] > arr[i+1]:
    i += 1

  return i == n-1

Key aspects are the single peak and the increasing then decreasing sequence. Bitonic sequences have applications in algorithms like bitonic sort.

A bitonic sequence is a sequence of numbers that initially increases and then decreases or vice versa. In other words, it has a peak or a trough. A sequence that only increases or only decreases is not bitonic.

For example, [1, 3, 5, 4, 2] is a bitonic sequence. The sequence increases from 1 to 5 and then decreases from 5 to 2.

Code Examples

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class BitonicSequence {
  public static void main(String[] args) {
    int[] arr = {1, 3, 5, 4, 2};
    System.out.println(isBitonic(arr));
  }

  public static boolean isBitonic(int[] arr) {
    int n = arr.length, i = 0;

    // Check for increasing
    while (i < n - 1 && arr[i] < arr[i + 1]) {
      i++;
    }

    // Check for decreasing
    while (i < n - 1 && arr[i] > arr[i + 1]) {
      i++;
    }

    return i == n - 1;
  }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;

bool isBitonic(int arr[], int n) {
  int i = 0;

  while (i < n - 1 && arr[i] < arr[i + 1]) {
    i++;
  }

  while (i < n - 1 && arr[i] > arr[i + 1]) {
    i++;
  }

  return i == n - 1;
}

int main() {
  int arr[] = {1, 3, 5, 4, 2};
  int n = sizeof(arr) / sizeof(arr[0]);

  cout << isBitonic(arr, n) << endl;

  return 0;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def is_bitonic(arr):
    n = len(arr)
    i = 0

    while i < n - 1 and arr[i] < arr[i + 1]:
        i += 1

    while i < n - 1 and arr[i] > arr[i + 1]:
        i += 1

    return i == n - 1

arr = [1, 3, 5, 4, 2]
print(is_bitonic(arr))

These code snippets examine an array to determine if it forms a bitonic sequence. They do so by first checking for increasing values and then checking for decreasing values. If both conditions are met, the function returns true.