852. Peak Index in a Mountain Array
Peak Index in a Mountain Array (LeetCode 852) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the Find Min/Max in Rotated Sorted Array subpattern.
How to solve Peak Index in a Mountain Array
Peak Index in a Mountain Array is a Binary Search in Rotated Sorted Array problem, part of Binary Search Patterns. Master binary search in rotated sorted arrays. Find minimum, search elements, and handle duplicates.
Work towards the solution in these steps:
- Consider using a binary search approach to achieve the required O(log n) time complexity instead of a linear scan.
- Think about how the properties of a mountain array (strictly increasing then strictly decreasing) can guide your search direction in binary search.
- At each step in binary search, compare the middle element with its next neighbor to determine if you are on the ascending or descending slope of the mountain.
The reference solution runs in O(logn) time and O(1) space.
The Peak Index in a Mountain Array solution and editorial walks through the full approach with reference code.
Problem statement
You are given an integer mountain array arr of length n where the values increase to a peak element and then decrease.
Return the index of the peak element.
Your task is to solve it in O(log(n)) 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.
Topics and companies
Topics: Array, Binary Search.
Reported in interviews at Bloomberg, Yahoo.
How to practise Peak Index in a Mountain Array on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(logn) time and O(1) space.
Open Peak Index in a Mountain Array in the code editor, or read the Peak Index in a Mountain Array editorial for a worked solution with its approach and complexity analysis.
Where Peak Index in a Mountain Array sits in the DSA pattern sheet
- Binary Search Patterns pattern guide
- Find Min/Max in Rotated Sorted Array subpattern
- The full DSA patterns sheet
Problems related to Peak Index in a Mountain Array
Other problems that use the same Find Min/Max in Rotated Sorted Array and Binary Search Patterns techniques:
- Find in Mountain Array — Hard, same subpattern
- Find Minimum in Rotated Sorted Array — Medium, same subpattern
- Find Peak Element — Medium, same subpattern
- Search in Rotated Sorted Array — Medium, same subpattern
- Search in Rotated Sorted Array II — Medium, same subpattern
- Binary Search — Easy, same pattern
Peak Index in a Mountain Array FAQ
What is the LeetCode number of Peak Index in a Mountain Array?
Peak Index in a Mountain Array is LeetCode problem 852, rated Medium.
What pattern is used to solve Peak Index in a Mountain Array?
Peak Index in a Mountain Array is a Binary Search in Rotated Sorted Array problem. It belongs to the Binary Search Patterns pattern, in the Find Min/Max in Rotated Sorted Array subpattern.
What is the time complexity of Peak Index in a Mountain Array?
The reference solution runs in O(logn) time and O(1) space.
Which companies ask Peak Index in a Mountain Array?
Peak Index in a Mountain Array has been reported in interviews at Bloomberg, Yahoo.