Home » Interview coding problems/challenges

Maximum value in a bitonic array

In this article, we are going to see how to find the maximum value in a bitonic array in optimized time complexity? This problem has been featured in interview coding round of Amazon.
Submitted by Radib Kar, on January 30, 2019

Problem statement:

Given a bitonic array find the maximum value of the array. An array is said to be bitonic if it has an increasing sequence of integers followed immediately by a decreasing sequence of integers.

Example:

Input:
1 4 8 3 2

Output:
8

Solution:

Definitely the brute force solution even works in linear time where you just pick each element and compare with the previous & next element. That’s pretty simple. But the concept of bitonic search leads up to more optimized solution reducing the number of comparison.

Algorithm:

Pre-requisite:

Bitonic array, low index (lower bound), high index (upper bound)

FUNCTION findMaxBitonic (Input array, low, high){
    While(low<=high){
        1.	Set mid to (low+high)/2;
        2.	Comparisons
        IF(array [mid]>array[mid-1] &&array[mid]>array[mid+1])
            Return array[mid]; //as this is the maximum
        //in the increasing region of the bitonic array
        IF(array[mid]>array[mid-1] &&array[mid]<array[mid+1]) 
            low=mid+1; //move lower bound up
        //in the decreasing region of the bitonic array
        ELSE IF(array[mid]<array[mid-1] &&array[mid+1]<array[mid])
            high=mid-1; //move upper bound down
    END WHILE
    IF control comes out of the loop
        //for trivial cases like array size 1 or 2
        return array[array size-1]; 
END FUNCTION

Time complexity: O(log(n))

C++ implementation

#include <bits/stdc++.h>
using namespace std;

//printing the array
void print(vector<int> a,int n){
	for(int i=0;i<n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
}


//function to find the max
int findMaxBitonic(vector<int> a,int low,int high){ 
	while(low<=high){
		int mid=(low+high)/2;

		if(a[mid]>a[mid-1] && a[mid]>a[mid+1]) //the maximum
			return a[mid];
		if(a[mid]>a[mid-1] && a[mid]<a[mid+1]) //in increasing zone
			low=mid+1;
		if(a[mid]<a[mid-1] && a[mid+1]<a[mid]) //in decreasing zone
			high=mid-1;
	}
	return a[a.size()-1];
}

int main(){
	int n,item;

	cout<<"enter array size: ";
	scanf("%d",&n);

	vector<int> a;

	cout<<"input bitonic array of size: "<<n<<endl;
	for(int j=0;j<n;j++){
		scanf("%d",&item);
		a.push_back(item);
	}
	cout<<"your bitonic array is:\n";
	print(a,n);
	cout<<"maximum in this bitonic array is:"<<findMaxBitonic(a,0,n-1)<<endl;
	
	return 0;
}

Output

First run:
enter array size: 5
input bitonic array of size: 5
1 4 8 3 2
your bitonic array is:
1 4 8 3 2
maximum in this bitonic array is:8

Second run:
enter array size: 10
input bitonic array of size: 10
6 8 20 12 11 9 7 5 0 -4
your bitonic array is:
6 8 20 12 11 9 7 5 0 -4
maximum in this bitonic array is:20

Explanation with example:

Input array, arr:
1 4 8 3 2
Array size: 5

In the main function we call findMaxBitonic (arr, 0, 4);
Input array = arr
low = 0
high = 4
-----------------------------------------------------------

findMaxBitonic (arr, 0, 4)
0th iteration
low<high (0<4)
mid= (low +high)/2 = 2
arr[mid]>arr[mid+1] && arr[mid]>arr[mid-1] // 8>4 && 8>3
return arr[mid] //return 8
maximum in the bitonic array=8

So, in this input case we only need one comparison, where if we had done in brute force, would have required 3 comparisons.