Home » Algorithms

Find the maximum element in an array which is first increasing and then decreasing

In this tutorial, we will learn how to search the maximum element of an array which is first increasing & then decreasing. This maximum element in such type of array is also known as peak element. By Radib Kar Last updated : August 10, 2023

Problem statement

Say, the array is like below,

[3, 10, 17, 15, 2, -3]

Then the peak element or the maximum element would be 17.

We can solve this both by linear search & binary search. The linear search algorithm will have the worst case time complexity of O(n) & the binary search algorithm will have worst-case time complexity of O(logN).

Using linear search

Since the array is increasing first & then decreasing so the maximum element would be the last one in the increasing series & the first one in the decreasing series. SO we can ignore the increasing part and check if the next element is decreasing or not. As soon as we find any element is greater than it's immediate next element on the right side, we can infer that as the peak element. The algorithm would ve like below,

for (int i = 1; i < arr.size(); i++) {
    if (arr[i] > arr[i + 1]) {
        peakNumber = arr[i];
        break;
    }
}

Using binary search

We can also solve this using binary search. We need to check whether our pivot element is in the increasing part or the decreasing part. If the pivot element is in the increasing part then we need to search only in the right part & if it's in the decreasing part then we need to search in the left part. The implementation is like following,

int findThePeakEfficientRecur(vector& arr, int start, int end)
{
    //base cases
    //only one element in array

    if (start == end)
        return arr[start];
    //if two element
    if (start + 1 == end) {
        return max(arr[start], arr[end]);
    }

    int mid = start + (end - start) / 2;

    //we got our peak
    if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) 
        return arr[mid];
    //pivot element is still in the increasing part
    else if (arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1]) { 
        return findThePeakEfficientRecur(arr, mid + 1, end);
    }
    else
        return findThePeakEfficientRecur(arr, start, mid - 1);
}

C++ program to find the maximum element in an array which is first increasing and then decreasing

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

//naive approach
void findThePeakNaive(vector<int>& arr)
{
    cout << "..............Using naive search......\n";

    //O(n) time complexity

    int peakNumber = -1;
    //if only one element
    if (arr.size() == 1)
        peakNumber = arr[0];
    //if two elements
    if (arr.size() == 2)
        peakNumber = max(arr[0], arr[1]);
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] > arr[i + 1]) {
            peakNumber = arr[i];
            break;
        }
    }
    if (peakNumber == -1)
        cout << "There is no peak element in this array\n";
    else
        cout << "The peak element(maximum number) is " << peakNumber << "\n";

    return;
}

//recursive binary search
int findThePeakEfficientRecur(vector<int>& arr, int start, int end)
{
    //base cases
    //only one element in array

    if (start == end)
        return arr[start];
    //if two element
    if (start + 1 == end) {
        return max(arr[start], arr[end]);
    }

    int mid = start + (end - start) / 2;

    //we got our peak
    if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) 
        return arr[mid];
    //pivot element is still in the increasing part
    else if (arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1]) { 
        return findThePeakEfficientRecur(arr, mid + 1, end);
    }
    else
        return findThePeakEfficientRecur(arr, start, mid - 1);
}

void findThePeakEfficient(vector<int>& arr)
{
    cout << "..............Using efficient approach(binary search)......\n";

    //O(logn) time complexity

    int peakNumber = findThePeakEfficientRecur(arr, 0, arr.size() - 1);

    if (peakNumber == -1)
        cout << "There is no peak element in this array\n";
    else
        cout << "The peak element(maximum number) is " << peakNumber << "\n";

    return;
}

int main()
{
    cout << "Enter number of elements\n";
    int n;
    cin >> n;
    vector<int> arr(n);
    cout << "Enter the elements(increasing first &  then decreasing)\n";

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    //using navive approach
    findThePeakNaive(arr);
    //using binary search
    findThePeakEfficient(arr);

    return 0;
}

Output

Enter number of elements
6
Enter the elements(increasing first &  then decreasing)
3 10 17 15 2 -3
..............Using naive search......
The peak element(maximum number) is 17
..............Using efficient approach(binary search)......
The peak element(maximum number) is 17