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.

New Comment