Leetcode 852: Peak Index in a Mountain Array
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.
Approach: We can solve this problem efficiently using a binary search approach to find the peak element in O(log n) time.
Observations:
• The array is a mountain array, meaning the elements first increase to a peak and then decrease.
• We can take advantage of the binary search technique by checking the middle element and adjusting our search bounds based on whether we are on the increasing or decreasing slope.
Steps:
• Step 1: Initialize `l` to 1 and `r` to `n - 2` (since the peak can't be at the boundaries).
• Step 2: While `l <= r`, calculate the middle index `mid`.
• Step 3: If `arr[mid]` is greater than both its neighbors, return `mid` as the peak index.
• Step 4: If the element at `mid` is greater than the element at `mid + 1`, it means the peak is on the left, so adjust `r = mid - 1`.
• Step 5: If the element at `mid` is less than the element at `mid + 1`, it means the peak is on the right, so adjust `l = mid + 1`.
Empty Inputs:
• N/A: The array always has at least 3 elements.
Large Inputs:
• The solution must efficiently handle cases where the array length is close to the upper limit (10^5).
Special Values:
• The array will always contain a valid peak, so there is no need for additional validity checks.
Constraints:
• The binary search approach ensures O(log n) time complexity.
int peakIndexInMountainArray(vector<int>& arr) {
int n = arr.size();
int l = 1, r = n - 2;
while(l <= r) {
int mid = l + (r - l + 1) / 2;
if(arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1]) {
return mid;
}
if(arr[mid] > arr[mid + 1]) {
r = mid - 1;
} else if(arr[mid] > arr[mid - 1]) {
l = mid + 1;
}
}
return 0;
}
1 : Function Definition
int peakIndexInMountainArray(vector<int>& arr) {
Defines the function that will return the index of the peak element in the mountain array.
2 : Variable Initialization
int n = arr.size();
Stores the size of the input array into variable 'n'.
3 : Variable Initialization
int l = 1, r = n - 2;
Initializes left and right pointers (l and r) to search within the range of valid indices.
4 : Looping
while(l <= r) {
Starts the binary search loop to find the peak.
5 : Mid Calculation
int mid = l + (r - l + 1) / 2;
Calculates the middle index (mid) for the binary search range.
6 : Condition Check
if(arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1]) {
Checks if the current element is greater than its neighbors, indicating it's the peak.
7 : Return
return mid;
Returns the index of the peak element.
8 : Condition Check
if(arr[mid] > arr[mid + 1]) {
If the current element is greater than the element on its right, move the right pointer.
9 : Pointer Update
r = mid - 1;
Updates the right pointer to search the left half of the array.
10 : Condition Check
} else if(arr[mid] > arr[mid - 1]) {
If the current element is greater than the element on its left, move the left pointer.
11 : Pointer Update
l = mid + 1;
Updates the left pointer to search the right half of the array.
12 : Return
return 0;
Returns 0 if no peak is found (default case).
Best Case: O(log n)
Average Case: O(log n)
Worst Case: O(log n)
Description: The time complexity is O(log n) due to the binary search process, which halves the search space at each step.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) as the solution uses only a constant amount of extra space.
LeetCode Solutions Library / DSA Sheets / Course Catalog |
---|
comments powered by Disqus