Posted on by Kalkicode
Code Array

# Print all bitonic subarray

The problem involves finding and printing all the bitonic subarrays within a given array. A bitonic subarray is a subarray in which the elements are first in increasing order and then in decreasing order, forming a peak. In this article, we'll dive into the problem statement, explain it with examples, provide an approach to solve it, present the pseudocode and algorithm, discuss the time complexity, and finally, explain the output.

## Problem Statement and Description

Given an array of integers, the task is to find and print all the bitonic subarrays present in the array. A bitonic subarray is characterized by a sequence of elements that first strictly increase and then strictly decrease. For instance, in the array [1, 2, 3, 2, 4, 5, 6, 3, 2, 1], the bitonic subarrays are [1, 2, 3, 2], [2, 3, 2], [2, 4, 5, 6, 3, 2, 1], [4, 5, 6, 3, 2, 1], [5, 6, 3, 2, 1], [1, 2, 3, 4, 3], [2, 3, 4, 3], and [3, 4, 3].

## Idea to Solve the Problem

To solve this problem, we can iterate through the array while keeping track of the current state. We will start with an initial state of no active bitonic subarray. As we traverse the array, we will detect the points where the subarray transitions from an increasing to a decreasing sequence, indicating the end of a bitonic subarray. We can then print the bitonic subarray within these boundaries.

## Pseudocode

``````function printBitonicSubarrays(arr):
counter = 0

for i from 0 to size-2:
stage = 0
x = -1

if arr[i] < arr[i+1]:
stage = 1

for j from i+1 to size-2:
x = j

if stage == 1 and arr[j] > arr[j+1]:
stage = 2
else if stage == 2 and arr[j] < arr[j+1]:
break

if stage == 2:
for k from i to x:
print arr[k]
counter = counter + 1

if counter == 0:
print "None"``````

## Algorithm Explanation

1. Initialize a counter to keep track of the number of valid bitonic subarrays.
2. Iterate through the array using a loop variable `i` from 0 to size-2.
3. Set the stage to 0 and x to -1. The stage represents the current state of bitonic subarray detection.
4. Check if the current element `arr[i]` is less than the next element `arr[i+1]`. If true, it indicates a possible bitonic subarray.
5. Set stage to 1, indicating the start of a potential bitonic subarray.
6. Iterate through the remaining elements of the array using another loop variable `j` starting from i+1.
7. Track the index `x` where the bitonic subarray might end.
8. If stage is 1 and the current element `arr[j]` is greater than the next element `arr[j+1]`, change the stage to 2, marking the start of the decreasing sequence.
9. If stage is 2 and the current element `arr[j]` is less than the next element `arr[j+1]`, it indicates the end of the bitonic subarray. Break out of the loop.
10. If stage is 2, a valid bitonic subarray has been detected.
11. Iterate through the indices from `i` to `x` and print the elements of the bitonic subarray.
12. Increment the counter to keep track of the valid bitonic subarrays.
13. After the loops, if no valid bitonic subarrays were found (counter is still 0), print "None."

## Code Solution

``````//C Program
//Print all bitonic subarray
#include <stdio.h>

//Find all bitonic Sub Array
void bitonic(int arr[],int size)
{
//Variables which are handling execution process
int stage = 0, x = -1, start = 0 ,end =0 ,counter = 0;

for (int i = 0; i < size-1; ++i)
{
//Set initial state
stage = 0, x = -1;

//When to adjacency array element [i] is less than [i+1]
//Then there are possible bitonic sequence
if(arr[i] < arr[i+1])
{
//Active state 1
stage=1;

for (int j = i+1; j < size-1; ++j)
{

//get index
x=j;

if(stage == 1 &&  arr[j] > arr[j+1])
{
//When starting the sequence of decrement element
stage = 2;
}
else if(stage == 2 &&  arr[j] < arr[j+1])
{
//bitonic sequence are ends
break;
}

}
//Confirm that the valid bitonic sequence is exist or not
if(stage == 2 )
{
//When valid bitonic sequece exist
for (int k = i; k <= x; ++k)
{
printf("%3d", arr[k]);
}
printf("\n");

counter++;
}
}
}
if(counter == 0)
{
//When no bitonic sequence are exist
printf("None\n");
}
}

int main()
{
//Define an array
int arr[] = {1,2,3,2,4,5,6,3,2,1,2,3,4,3,9};
//Get the size
int size = sizeof(arr)/sizeof(arr[0]);

bitonic(arr,size);

return 0;
}```
```

#### Output

``````  1  2  3  2
2  3  2
2  4  5  6  3  2  1
4  5  6  3  2  1
5  6  3  2  1
1  2  3  4  3
2  3  4  3
3  4  3``````
``````//Node Js program
//Print all bitonic subarray
class MyArray {
//Find all bitonic Sub Array
bitonic(arr, size) {
//Variables which are handling execution process
var stage = 0;
var x = -1;
var start = 0;
var end = 0;
var counter = 0;
for (var i = 0; i < size - 1; ++i) {
//Set initial state
stage = 0;
x = -1;
//When to adjacency array element [i] is less than [i+1]
//Then there are possible bitonic sequence

if (arr[i] < arr[i + 1]) {
//Active state 1
stage = 1;
for (var j = i + 1; j < size - 1; ++j) {
//get index
x = j;
if (stage == 1 &&
arr[j] > arr[j + 1]) {
//When starting the sequence of decrement element
stage = 2;
} else
if (stage == 2 &&
arr[j] < arr[j + 1]) {
break;
}
}

//Confirm that the valid bitonic sequence is exist or not

if (stage == 2) {
//When valid bitonic sequece exist

for (var k = i; k <= x; ++k) {
process.stdout.write(" " + arr[k]);
}

process.stdout.write("\n");
counter++;
}
}
}

if (counter == 0) {
//When no bitonic sequence are exist

process.stdout.write("None");
}
}
}

function main(args) {
var obj = new MyArray();
//Define an array
var arr = [1, 2, 3, 2, 4, 5, 6, 3, 2, 1, 2, 3, 4, 3, 9];
//Get the size
var size = arr.length;
obj.bitonic(arr, size);
}

main();```
```

#### Output

`````` 1 2 3 2
2 3 2
2 4 5 6 3 2 1
4 5 6 3 2 1
5 6 3 2 1
1 2 3 4 3
2 3 4 3
3 4 3``````
``````# Ruby program
# Print all bitonic subarray
class MyArray
# Find all bitonic Sub Array
def bitonic(arr, size)
stage = 0
x = -1
start = 0
counter = 0
i = 0
while (i < size - 1)
# Set initial state
stage = 0
x = -1
# When to adjacency array element [i] is less than [i+1]
# Then there are possible bitonic sequence

if (arr[i] < arr[i + 1])
# Active state 1
stage = 1
j = i + 1
while (j < size - 1)
# get index
x = j
if (stage == 1 &&
arr[j] > arr[j + 1])
# When starting the sequence of decrement element
stage = 2
elsif (stage == 2 &&
arr[j] < arr[j + 1])
break
end
j += 1
end
# Confirm that the valid bitonic sequence is exist or not

if (stage == 2)
# When valid bitonic sequece exist
k = i
while (k <= x)
print(" ", arr[k])
k += 1
end
print("\n")
counter += 1
end
end
i += 1
end
if (counter == 0)
print("None")
end
end
end
def main()
obj = MyArray.new()
arr = [1, 2, 3, 2, 4, 5, 6, 3, 2, 1, 2, 3, 4, 3, 9]
size = arr.length
obj.bitonic(arr, size)
end
main()```
```

#### Output

`````` 1 2 3 2
2 3 2
2 4 5 6 3 2 1
4 5 6 3 2 1
5 6 3 2 1
1 2 3 4 3
2 3 4 3
3 4 3
``````
``````//Scala program
//Print all bitonic subarray
class MyArray {
//Find all bitonic Sub Array
def bitonic(arr: Array[Int], size: Int): Unit = {
var stage: Int = 0;
var x: Int = -1;
var start: Int = 0;
var counter: Int = 0;
var i: Int = 0;
while (i < size - 1) {
//Set initial state
stage = 0;
x = -1;

//When to adjacency array element [i] is less than [i+1]
//Then there are possible bitonic sequence

if (arr(i) < arr(i + 1)) {
//Active state 1
stage = 1;
var j: Int = i + 1;
while (j < size - 1) {
//get index
x = j;

if (stage == 1 &&
arr(j) > arr(j + 1)) {
//When starting the sequence of decrement element
stage = 2;
} else
if (stage == 2 &&
arr(j) < arr(j + 1)) {
//break loop in this case
j = size;
}
j += 1;
}
//Confirm that the valid bitonic sequence is exist or not
if (stage == 2) {
//When valid bitonic sequece exist
var k: Int = i;
while (k <= x) {
print(" " + arr(k));
k += 1;
}
print("\n");
counter += 1;
}
}
i += 1;
}
if (counter == 0) {
print("None");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
var arr: Array[Int] = Array(1, 2, 3, 2, 4, 5, 6, 3, 2, 1, 2, 3, 4, 3, 9);
var size: Int = arr.length;
obj.bitonic(arr, size);
}
}```
```

#### Output

`````` 1 2 3 2
2 3 2
2 4 5 6 3 2 1
4 5 6 3 2 1
5 6 3 2 1
1 2 3 4 3
2 3 4 3
3 4 3``````
``````//Swift program
//Print all bitonic subarray
class MyArray {
//Find all bitonic Sub Array
func bitonic(_ arr: [Int], _ size: Int) {
var stage: Int = 0;
var x: Int = -1;
var counter: Int = 0;
var i: Int = 0;
while (i < size - 1) {
//Set initial state
stage = 0;
x = -1;
//When to adjacency array element [i] is less than [i+1]
//Then there are possible bitonic sequence

if (arr[i] < arr[i + 1]) {
//Active state 1
stage = 1;
var j: Int = i + 1;
while (j < size - 1) {
//get index
x = j;
if (stage == 1 &&
arr[j] > arr[j + 1]) {
//When starting the sequence of decrement element
stage = 2;
} else
if (stage == 2 &&
arr[j] < arr[j + 1]) {
break;
}
j += 1;
}
//Confirm that the valid bitonic sequence is exist or not

if (stage == 2) {
//When valid bitonic sequece exist
var k: Int = i;
while (k <= x) {
print(" ", arr[k], terminator: "");
k += 1;
}
print("\n", terminator: "");
counter += 1;
}
}
i += 1;
}
if (counter == 0) {
print("None", terminator: "");
}
}
}
func main() {
let obj: MyArray = MyArray();
let arr: [Int] = [1, 2, 3, 2, 4, 5, 6, 3, 2, 1, 2, 3, 4, 3, 9];
let size: Int = arr.count;
obj.bitonic(arr, size);
}
main();```
```

#### Output

``````  1  2  3  2
2  3  2
2  4  5  6  3  2  1
4  5  6  3  2  1
5  6  3  2  1
1  2  3  4  3
2  3  4  3
3  4  3``````
``````# Python 3 program
# Print all bitonic subarray
class MyArray :
# Find all bitonic Sub Array
def bitonic(self, arr, size) :
x = -1
start = 0
counter = 0
i = 0
while (i < size - 1) :
# Set initial state
stage = 0
x = -1
# When to adjacency array element [i] is less than [i+1]
# Then there are possible bitonic sequence

if (arr[i] < arr[i + 1]) :
# Active state 1
stage = 1
j = i + 1
while (j < size - 1) :
# get index
x = j
if (stage == 1 and arr[j] > arr[j + 1]) :
# When starting the sequence of decrement element
stage = 2
elif (stage == 2 and arr[j] < arr[j + 1]) :
break

j += 1

# Confirm that the valid bitonic sequence is exist or not

if (stage == 2) :
# When valid bitonic sequece exist
k = i
while (k <= x) :
print(" ", arr[k], end = "")
k += 1

print("\n", end = "")
counter += 1

i += 1

if (counter == 0) :
print("None", end = "")

def main() :
obj = MyArray()
arr = [1, 2, 3, 2, 4, 5, 6, 3, 2, 1, 2, 3, 4, 3, 9]
size = len(arr)
obj.bitonic(arr, size)

if __name__ == "__main__":
main()```
```

#### Output

``````  1  2  3  2
2  3  2
2  4  5  6  3  2  1
4  5  6  3  2  1
5  6  3  2  1
1  2  3  4  3
2  3  4  3
3  4  3``````
``````//C++ program
//Print all bitonic subarray
#include<iostream>

using namespace std;
class MyArray {
public:

//Find all bitonic Sub Array
void bitonic(int arr[], int size) {
int x = -1, start = 0, counter = 0;
int i = 0;
int stage = 0;
while (i < size - 1) {
//Set initial state
stage = 0;
x = -1;
//When to adjacency array element [i] is less than [i+1]
//Then there are possible bitonic sequence

if (arr[i] < arr[i + 1]) {
//Active state 1
stage = 1;
int j = i + 1;
while (j < size - 1) {
//get index
x = j;
if (stage == 1 &&
arr[j] > arr[j + 1]) {
//When starting the sequence of decrement element
stage = 2;
} else
if (stage == 2 &&
arr[j] < arr[j + 1]) {
//bitonic sequence are ends

break;
}++j;
}
//Confirm that the valid bitonic sequence is exist or not

if (stage == 2) {
//When valid bitonic sequece exist
int k = i;
while (k <= x) {
cout << " " << arr[k];
++k;
}
cout << "\n";
counter++;
}
}++i;
}
if (counter == 0) {
cout << "None";
}
}
};
int main() {
MyArray obj = MyArray();
int arr[] = {
1,
2,
3,
2,
4,
5,
6,
3,
2,
1,
2,
3,
4,
3,
9
};
int size = sizeof(arr) / sizeof(arr[0]);
obj.bitonic(arr, size);
return 0;
}```
```

#### Output

`````` 1 2 3 2
2 3 2
2 4 5 6 3 2 1
4 5 6 3 2 1
5 6 3 2 1
1 2 3 4 3
2 3 4 3
3 4 3``````
``````//Java program
//Print all bitonic subarray
public class MyArray
{
//Find all bitonic Sub Array
public void  bitonic(int []arr,int size)
{
//Variables which are handling execution process
int stage = 0, x = -1, start = 0 ,end =0 ,counter = 0;
for (int i = 0; i < size-1; ++i)
{
//Set initial state
stage = 0;
x = -1;
//When to adjacency array element [i] is less than [i+1]
//Then there are possible bitonic sequence
if(arr[i] < arr[i+1])
{
//Active state 1
stage=1;

for (int j = i+1; j < size-1; ++j)
{

//get index
x=j;

if(stage == 1 &&  arr[j] > arr[j+1])
{
//When starting the sequence of decrement element
stage = 2;
}
else if(stage == 2 &&  arr[j] < arr[j+1])
{
//bitonic sequence are ends
break;
}

}
//Confirm that the valid bitonic sequence is exist or not
if(stage == 2 )
{
//When valid bitonic sequece exist
for (int k = i; k <= x; ++k)
{
System.out.print(" "+ arr[k]);
}
System.out.println();
counter++;
}
}
}
if(counter == 0)
{
//When no bitonic sequence are exist
System.out.println("None");
}
}
public static void main(String[] args)
{

MyArray obj = new MyArray();

//Define an array
int arr[] = {1,2,3,2,4,5,6,3,2,1,2,3,4,3,9};
//Get the size
int size = arr.length;

obj.bitonic(arr,size);

}
}```
```

#### Output

``````  1  2  3  2
2  3  2
2  4  5  6  3  2  1
4  5  6  3  2  1
5  6  3  2  1
1  2  3  4  3
2  3  4  3
3  4  3``````
``````<?php
//Php program
//Print all bitonic subarray
class MyArray {
//Find all bitonic Sub Array

public 	function bitonic( & \$arr, \$size) {
\$x = -1;
\$start = 0;
\$counter = 0;
\$i = 0;
while (\$i < \$size - 1) {
//Set initial state
\$stage = 0;
\$x = -1;
//When to adjacency array element [i] is less than [i+1]
//Then there are possible bitonic sequence

if (\$arr[\$i] < \$arr[\$i + 1]) {
//Active state 1
\$stage = 1;
\$j = \$i + 1;
while (\$j < \$size - 1) {
//get index
\$x = \$j;
if (\$stage == 1 &&
\$arr[\$j] > \$arr[\$j + 1]) {
//When starting the sequence of decrement element
\$stage = 2;
} else
if (\$stage == 2 &&
\$arr[\$j] < \$arr[\$j + 1]) {
break;
}++\$j;
}
//Confirm that the valid bitonic sequence is exist or not

if (\$stage == 2) {
//When valid bitonic sequece exist
\$k = \$i;
while (\$k <= \$x) {
echo(" ". \$arr[\$k]);
++\$k;
}
echo("\n");
\$counter++;
}
}++\$i;
}
if (\$counter == 0) {
echo("None");
}
}
}

function main() {
\$obj = new MyArray();
\$arr = array(1, 2, 3, 2, 4, 5, 6, 3, 2, 1, 2, 3, 4, 3, 9);
\$size = count(\$arr);
\$obj->bitonic(\$arr, \$size);

}
main();```
```

#### Output

`````` 1 2 3 2
2 3 2
2 4 5 6 3 2 1
4 5 6 3 2 1
5 6 3 2 1
1 2 3 4 3
2 3 4 3
3 4 3``````
``````//C# program
//Print all bitonic subarray
using System;
public class MyArray {
//Find all bitonic Sub Array
public void bitonic(int[] arr, int size) {
int x = -1, counter = 0;
int i = 0;
int stage = 0;
while (i < size - 1) {
//Set initial state
stage = 0;
x = -1;
//When to adjacency array element [i] is less than [i+1]
//Then there are possible bitonic sequence

if (arr[i] < arr[i + 1]) {
//Active state 1
stage = 1;
int j = i + 1;
while (j < size - 1) {
//get index
x = j;
if (stage == 1 &&
arr[j] > arr[j + 1]) {
//When starting the sequence of decrement element
stage = 2;
} else
if (stage == 2 &&
arr[j] < arr[j + 1]) {
break;;
}
j++;
}
//Confirm that the valid bitonic sequence is exist or not

if (stage == 2) {
//When valid bitonic sequece exist
int k = i;
while (k <= x) {
Console.Write(" " + arr[k]);
k++;
}
Console.Write("\n");
counter++;
}
}
i++;
}
if (counter == 0) {
Console.WriteLine("None");
}
}
public static void Main(String[] args) {
MyArray obj = new MyArray();
int[] arr = {
1,
2,
3,
2,
4,
5,
6,
3,
2,
1,
2,
3,
4,
3,
9
};
int size = arr.Length;
obj.bitonic(arr, size);
}
}```
```

#### Output

`````` 1 2 3 2
2 3 2
2 4 5 6 3 2 1
4 5 6 3 2 1
5 6 3 2 1
1 2 3 4 3
2 3 4 3
3 4 3``````

## Time Complexity

The time complexity of the provided code is primarily determined by the nested loops. The outer loop runs for `size-1` iterations, and the inner loop, in the worst case, also runs for `size-1` iterations. Therefore, the overall time complexity is O(n^2), where n is the size of the input array.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post