Peak Element Index — Problem Statement & Solution Guide
Problem Description
Given an array of integers heights representing recorded measurements, find the index of the peak element, where a peak element is greater than or equal to its neighboring elements. If multiple peak elements exist, return the first one.
Examples
Input
[1, 2, 3, 2, 1]
Output
1
Explanation: Step-by-step: We start from the first element. Since 1 is not greater than its neighbors, we move to the next element. 2 is greater than its neighbors, so we return its index, which is 1.
Input
[5, 4, 3, 2, 1]
Output
0
Explanation: Step-by-step: We start from the first element. Since 5 is greater than its neighbors, we return its index, which is 0.
Constraints
- 1 <= oxygen_levels.length <= 1000
- 0 <= oxygen_levels[i] <= 10000
Optimal Approach & Strategy
The optimal approach is to use a modified binary search algorithm, which can find the peak element in O(log n) time complexity by repeatedly dividing the search space in half.
Brute Force Approach
The brute-force approach would be to check each element in the array and compare it with its neighbors to find the peak element, resulting in a time complexity of O(n).
Verified Code Solutions
function peakElementIndex(heights) {
if (heights.length === 0) return 0;
let max = heights[0];
let maxIndex = 0;
for (let i = 1; i < heights.length; i++) {
if (heights[i] >= max) {
max = heights[i];
maxIndex = i;
}
}
return maxIndex;
}class Solution {
public int peakElement(int[] heights) {
int peak_idx = 0;
for (int i = 1; i < heights.length - 1; i++) {
if (heights[i] > heights[i - 1] && heights[i] > heights[i + 1]) {
peak_idx = i;
}
}
return peak_idx;
}
}def peakElement(heights):
# Initialize the peak element index to 0
peak_idx = 0
# Iterate through the array from the second element to the second last element
for i in range(1, len(heights) - 1):
# If the current element is greater than its neighbors, update the peak element index
if heights[i] > heights[i - 1] and heights[i] > heights[i + 1]:
peak_idx = i
# Return the peak element index
return peak_idxfunction peakElementIndex(heights) {
if (heights.length === 0) return 0;
let max = heights[0];
let maxIndex = 0;
for (let i = 1; i < heights.length; i++) {
if (heights[i] >= max) {
max = heights[i];
maxIndex = i;
}
}
return maxIndex;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.