DEV Community

Cover image for DAY 52 - Peak Index in a Mountain Array
Nayan Pahuja
Nayan Pahuja

Posted on • Edited on

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

Complexity Analysis:

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

Reinvent your career. Join DEV.

It takes one minute and is worth it for your career.

Get started

Top comments (0)

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay