Find Maximum in First Increasing and then Decreasing Array

Difficulty: Easy, Asked-in: Microsoft, Amazon, Adobe, Goldman Sachs, Walmart

Key takeaway: This is a good interview problem to learn problem-solving using binary search. The solution idea is intuitive where we modify the binary search algorithm to improve the time complexity.

Let's understand the problem

You are given an array of integers that is initially increasing and then decreasing, find the maximum value in the array. Hint: keep in mind the corner cases.

Example 1

Input: X[] = [18, 110, 210, 452, 810, 500, 101, 13], Output: 810

Explanation: Array is increasing from start to value 500 and then decreasing. So maximum value in the array = 810

Example 2

Input: X[] = [1, 2, 3, 4, 5], Output: 5

Explanation: Array is sorted in increasing order. So maximum value in the array = 5

Discussed solution approaches

• Brute force approach using linear search
• Efficient approach  using binary search

Brute force approach  using linear search

Solution idea and steps

A simple approach is to traverse the array linearly and find the maximum.

• We initialize a variable max with the first element to track the maximum element.
• Now we traverse from the second element to the last element using a loop.
• When we find a value A[i] greater than max, we update max with A[i] and continue this process until the values in the array keep increasing. In other words, our max value is at the peak, and we reach thereby updating the variable max with A[i].
• We need to stop at the peak point because, after that, the array values start decreasing. In other words, when we first time find some A[i] < max, we break the loop and return the value stored in the max.

Solution pseudocode

int max_inc_dec(int A[], int low, int high)
{
    int max = A[low]  
    for (int i = low + 1; i <= high; i = i + 1)
    {
        if(A[i] > max)
            max = A[i]
        else 
            break
    }
    return max
}

Python implementation

def max_inc_dec(A, low, high):
    max = A[low]  
    for i in range(low + 1, high + 1):
        if A[i] > max:
            max = A[i]
        else:
            break
    return max

Solution analysis

The worst case occurs when the array is sorted in increasing order, and we need to traverse each element till the end. So worst-case time complexity = O(n). What would be the best and average-case time complexity? Think! We are using a constant number of variables, so space complexity = O(1)

But the critical question is: how can we improve the time complexity? How do we use the ‘first increasing and then decreasing’ property given in the input to enhance the solution's efficiency? Think!

Efficient approach  using binary search

Solution idea and steps

In the ‘first increasing and then decreasing’ array, the max value in the array would be the peak point or a point after which the values started decreasing. One intuition of the efficient solution is — can we apply the idea of binary search to find such a specific point because elements in the array are sorted in a particular order? But how do we use the concept of binary search? Think! Here are the observations to modify the standard binary search algorithm:

• If the mid element is greater than both of its adjacent elements, then the value at mid is the maximum. In other words, the array is decreasing after the midpoint i.e. if (A[mid] > A[mid-1] && A[mid] > A[mid+1]), then we return A[mid].
• If the mid element is greater than its next element and smaller than the previous element then maximum lies on the left sub-array i.e. if (A[mid] > A[mid+1] && A[mid] < A[mid-1]) then we search max in the left subarray. In other words, we are on the decreasing side of the array and the peak will be somewhere between low to mid - 1. Think!
• If the mid element is smaller than its next element and greater than the previous element then maximum lies on the right sub-array i.e. if (A[mid] < A[mid+1] && A[mid] > A[mid-1]) then we search max in the right subarray.In other words, we are on the increasing side of the array and the peak will be somewhere between mid + 1 to high. Think!

Solution pseudocode 

int max_inc_dec(int A[], int low, int high)
{
    if (low == high)
        return A[low]
    if ((high == low + 1) && A[low] >= A[high])
        return A[low]
    if ((high == low + 1) && A[low] < A[high])
        return A[high]
 
    int mid = low + (high - low)/2
    if (A[mid] > A[mid + 1] && A[mid] > A[mid - 1])
        return A[mid]
 
    if (A[mid] > A[mid + 1] && A[mid] < A[mid - 1])
        return max_inc_dec(A, low, mid-1)
    else
        return max_inc_dec(A, mid + 1, high)
}

Python implementation

def max_inc_dec(A, low, high):
    if low == high:
        return A[low]
    if (high == low + 1) and A[low] >= A[high]:
        return A[low]
    if (high == low + 1) and A[low] < A[high]:
        return A[high]

    mid = low + (high - low) // 2
    if A[mid] > A[mid + 1] and A[mid] > A[mid - 1]:
        return A[mid]

    if A[mid] > A[mid + 1] and A[mid] < A[mid - 1]:
        return max_inc_dec(A, low, mid - 1)
    else:
        return max_inc_dec(A, mid + 1, high)

Solution analysis

Since we are using recursive binary search, so the time complexity of the above program would be O(log n). The space complexity depends on the size of the call stack which is equal to the height of the recursion tree. So space complexity = O(logn). Think!

Critical ideas to think about!

• How do we implement the efficient approach using the iterative binary search?
• Does the binary search solution correct If the array contains duplicates? If not then, how do we modify the solution to work for duplicate elements?
• How to modify the above code to cover edge cases when the array is purely increasing or purely decreasing?
• How do we modify the above code if we have to find a minimum value when the array is first decreasing and increasing?

Comparisons of time and space complexities

• Linear search: Time = O(n), Space = O(1)
• Using recursive binary search: Time = O(logn), Space = O(logn)

Coding problems to practice using binary search

• Find peak element
• Search a sorted 2D matrix
• Find the square root of an integer
• Find smallest letter greater than target
• Median of two sorted arrays
• Search in rotated sorted array
• Search a 2D matrix II
• Find minimum in rotated sorted array
• Find the index of the first 1 in an infinite sorted array of 0s and 1s
• Find the element that appears once in a sorted array

Thanks to Navtosh Kumar for his contribution in creating the first version of the content. Enjoy learning, Enjoy coding, Enjoy algorithms!