Leet Code Problem 852 — Peak Index in a Mountain Array
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(logn) time complexity.
- Input: nums = [0,1,0]
- Output: 1
- Input: nums = [0,2,1,0]
- Output: 1
- Input: nums = [0,10,5,2]
- Output: 1
The code is attempting to find the peak index in a “mountain array” (an array that increases to a maximum point and then decreases). Here’s a breakdown of the approach:
1. Binary Search: The code applies a binary search on the array to reduce the time complexity to O (log n).
2. Peak Condition: For each midpoint `medium`, it checks:
- If the element at `medium` is greater than both its neighbouring elements (`left` and `right`), then `medium` is the peak, and it returns `medium`.
3. Directional Adjustment:
- If `medium` is part of an ascending slope (`middle > left && middle < right`), it moves the search to the right half (`start = medium + 1`).
- If `medium` is part of a descending slope (`middle < left && middle > right`), it moves the search to the left half (`end = medium — 1`).
4. Close Proximity Condition: If `end — start == 1`, it directly compares `arr[start]` and `arr[end]` to return the larger value’s index.
class Solution
{
public:
int peakIndexInMountainArray(vector<int> &arr)
{
int start = 0;
int end = arr.size() - 1;
while (start <= end)
{
int medium = start + ((end - start) / 2);
int left = arr.at(medium - 1);
int right = arr.at(medium + 1);
int middle = arr.at(medium);
if (middle > left && middle > right)
{
return medium;
}
else if (middle > left && middle < right)
{
start = medium + 1;
}
else if (middle < left && middle > right)
{
end = medium - 1;
}
if (end - start == 1)
{
if (arr.at(start) > arr.at(end))
{
return start;
}
else
{
return end;
}
}
}
}
};
