Algorithm

Problem Name: 852. Peak Index in a Mountain Array

Problem Link: https://leetcode.com/problems/peak-index-in-a-mountain-array/

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 = [0,2,1,0]
Output: 1

Example 3:

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

 

Constraints:

  • 3 <= arr.length <= 105
  • 0 <= arr[i] <= 106
  • arr is guaranteed to be a mountain array.
 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {
        int n = A.size();
        // O(n)
        for (int i = 1; i  <  n - 1; ++i) {
            if (A[i] > A[i - 1] && A[i] > A[i + 1]) {
                return i;
            }
        }
        
        // O(logn)
        int l = 1, r = n - 2, mid;
        while (l  < = r) {
            mid = l + (r - l)/2;
            if (A[mid] > A[mid - 1] && A[mid] > A[mid + 1]) {
                return mid;
            } else if (A[mid] > A[mid - 1]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return -1;
    }
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
arr = [0,1,0]

Output

x
–
+
cmd
1

#2 Code Example with Python Programming

Code - Python Programming


class Solution:
    def peakIndexInMountainArray(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        mx = max(A)
        return A.index(mx)
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
arr = [0,1,0]

Output

x
–
+
cmd
1

#3 Code Example with C# Programming

Code - C# Programming


namespace LeetCode
{
    public class _0852_PeakIndexInAMountainArray
    {
        public int PeakIndexInMountainArray(int[] A)
        {
            int lo = 0, hi = A.Length - 1;
            while (lo  <  hi)
            {
                var mid = lo + (hi - lo) / 2;
                if (A[mid] < A[mid + 1])
                    lo = mid + 1;
                else
                    hi = mid;
            }

            return lo;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
arr = [0,2,1,0]

Output

x
–
+
cmd
1
Advertisements

Demonstration

Previous
#851 Leetcode Loud and Rich Solution in Python Leetcode
Next
#853 Leetcode Car Fleet Solution in C++, Python Leetcode