DAY 52 - Peak Index in a Mountain Array

Nayan Pahuja - Jul 25 '23 - - Dev Community

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

Complexity Analysis:

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .