Peak Index In A Mountain Array Problem


Description

LeetCode Problem 852.

Let’s call an array arr a mountainif the following properties hold:

  • arr.length >= 3
  • There exists some i with0 < i< arr.length - 1such that:
  • arr[0] < arr[1] < … arr[i-1] < arr[i]
  • arr[i] > arr[i+1] > … > arr[arr.length - 1]

Given an integer array arr that is guaranteed to bea mountain, return anyisuch thatarr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1].

Example 1:

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

Example 2:

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

Example 3:

1
2
Input: arr = [0,10,5,2]
Output: 1

Example 4:

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

Example 5:

1
2
Input: arr = [24,69,100,99,79,78,67,36,26,19]
Output: 2

Constraints:

  • 3 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^6
  • arr is guaranteed to be a mountain array.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int low = 0, high = arr.size()-1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] < arr[mid+1])
                low = mid + 1;
            else
                high = mid - 1;
        }
        return low;
    }
};




Related Posts

Super Egg Drop Problem

LeetCode 887. You are given k identical eggs and you...

Peak Index In A Mountain Array Problem

LeetCode 852. Let’s call an array arr a mountainif the...

Numbers At Most N Given Digit Set Problem

LeetCode 902. Given an array of digits which is sorted...

Nth Magical Number Problem

LeetCode 878. A positive integer is magical if it is...

Koko Eating Bananas Problem

LeetCode 875. Koko loves to eat bananas. There are n...