DAY 52 - Peak Index in a Mountain Array

Question:

An array arr a mountain if the following properties hold:

arr.length >= 3
There exists some i with 0 < i < arr.length - 1 such that:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given a mountain array arr, return the index i _such that _arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

You must solve it in O(log(arr.length)) time complexity.

Example 1:

Input: arr = [0,1,0]
Output: 1

Example 2:

Input: arr = [1,2,3,2,1]
Output: 2

Intuition:

• Let's start with breaking down the question.
• Basically we are given an array which contains two parts inside an array.
• One which is in strictly increasing order and after that one which is strictly in decreasing order.
• Example: {1,2,3,4,5,4,3,2,1}
• Now it's obvious that there will be an element which separates those two sections is 5.

• Here we need to find that element's index.

• We can look this as two arrays who are sorted, one in increasing order and one in decreasing order.

• We can use binary search that is applicable on sorted arrays to find our element.

• Refer to algorithm for more understanding.

Algorithm: Binary Search

Initializing variables:

• We need two variables start and end which refer to our starting and ending points in a binary search.
• MID of an array is nothing but (start + end )/2.

Traversion:

• We then traverse the array and find the middle each time our loop runs.
• If the element we are currently at is less than the element it's next , it means we are in the left section(strictly increasing section) of our array and need to go ahead. So we jump our start to mid+1.
• If it's not greater , it consequently means we are in the right section of our array and need to shift our end back to the mid element.

• When we are not able to traverse anymore that's when our start and end have reached an element that satisfies neither of the if conditions.

• Hence we return our answer which is the element start is pointing to.

Code:

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int start = 0;
        int end = arr.size() -1;

        while (start < end){
            int mid = start + (end-start)/2;
            if (arr[mid] < arr[mid+1]){
                start = mid +1;
            }
            else{
                end = mid;
            }


        }
        return start;
    }
};

Complexity Analysis:

Time: O(logN)
Space: O(1)