Leetcode 852: Peak Index in a Mountain Array

grid47
grid47
Exploring patterns and algorithms
Aug 13, 2024 6 min read

You are given a mountain array arr of length n, where the values first strictly increase to a peak element and then strictly decrease. Your task is to find the index of the peak element in the array. The peak element is an element that is greater than both its neighbors.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer array `arr` that represents the mountain array.
Example: Input: arr = [1, 3, 2]
Constraints:
• 3 <= arr.length <= 10^5
• 0 <= arr[i] <= 10^6
• arr is guaranteed to be a mountain array.
Output: Return the index of the peak element in the array.
Example: Output: 1
Constraints:
Goal: The goal is to find the index of the peak element in O(log(n)) time complexity using binary search.
Steps:
• Step 1: Initialize two pointers, `l` and `r`, to represent the left and right bounds of the search range.
• Step 2: Use binary search to find the peak element by comparing the middle element with its neighbors.
• Step 3: If the middle element is greater than both neighbors, return its index.
• Step 4: If the middle element is less than its right neighbor, move the left pointer to `mid + 1`. Otherwise, move the right pointer to `mid - 1`.
Goal: The array is guaranteed to be a valid mountain array, so no need to check for validity.
Steps:
• The array will always contain at least 3 elements.
Assumptions:
• The array is a valid mountain array, which means there is always exactly one peak.
Input: Input: arr = [0, 2, 1, 0]
Explanation: In this example, the peak element is 2, which is located at index 1. The values increase from index 0 to 1, and then decrease from index 1 to 3, so the peak is at index 1.

Input: Input: arr = [0, 10, 5, 2]
Explanation: Here, the peak element is 10, located at index 1. The values increase from index 0 to 1, and then decrease from index 1 to 3, with 10 being the peak.

Link to LeetCode Lab


LeetCode Solutions Library / DSA Sheets / Course Catalog
comments powered by Disqus