BackmediumArraysMicrosoft

Peak Element Index 2 Solution

Problem Statement

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 the input array is empty, return -1.

Example 1
Input
[1, 2, 3, 2, 1]
Output
2

Explanation: Step-by-step: Given the input array [1, 2, 3, 2, 1], we first check if the first element is greater than or equal to its neighboring elements. Since 1 is not greater than or equal to its neighboring elements, we move to the next element. We continue this process until we find the peak element at index 2, which is 3. Therefore, the output is 2.

Example 2
Input
[5, 4, 3, 2, 1]
Output
0

Explanation: Step-by-step: Given the input array [5, 4, 3, 2, 1], we first check if the first element is greater than or equal to its neighboring elements. Since 5 is greater than or equal to its neighboring elements, we return 0 as the index of the peak element.

Constraints

  • 1 <= oxygen_levels.length <= 1000
  • 0 <= oxygen_levels[i] <= 10000

More Arrays

Move Zeros to EndeasySorted SquareseasyFind Balance IndexeasyPartition Even OddeasyFirst Duplicate NodeeasyFind Missing IndiceseasyCumulative Array SumeasyRange Sum Query Using Prefix Sumeasy
View all problems ā†’
Live Compiler1 Free Run Available
Loading Editor...
Test Cases & Output
Click "Run" to test your 1 free compile trial!

šŸš€ Practice this problem

Run code, get AI hints & track streak

Sign Up Free

Peak Element Index 2 ā€” Problem Statement & Solution Guide

ArraysMediumModified Binary Search
TimeO(n)
|
SpaceO(1)

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 the input array is empty, return -1.

Examples

Example 1

Input

[1, 2, 3, 2, 1]

Output

2

Explanation: Step-by-step: Given the input array [1, 2, 3, 2, 1], we first check if the first element is greater than or equal to its neighboring elements. Since 1 is not greater than or equal to its neighboring elements, we move to the next element. We continue this process until we find the peak element at index 2, which is 3. Therefore, the output is 2.

Example 2

Input

[5, 4, 3, 2, 1]

Output

0

Explanation: Step-by-step: Given the input array [5, 4, 3, 2, 1], we first check if the first element is greater than or equal to its neighboring elements. Since 5 is greater than or equal to its neighboring elements, we return 0 as the index of the peak element.

Constraints

  • 1 <= oxygen_levels.length <= 1000
  • 0 <= oxygen_levels[i] <= 10000

Optimal Approach & Strategy

The optimal approach involves using a modified binary search algorithm to find the peak oxygen level in the array, resulting in a time complexity of O(log n). This approach takes advantage of the fact that the peak oxygen level must be greater than or equal to its neighbors.

Brute Force Approach

The brute-force approach involves checking every element in the array and comparing it to its neighbors, resulting in a time complexity of O(nĀ²). This approach is inefficient and should be avoided for large arrays. A naive approach would involve checking each element individually, resulting in a time complexity of O(n).

Verified Code Solutions

JavaScript Solution
Time: O(n)
function solution(heights) {
   if (heights.length === 0) return -1;
   let peakIndex = 0;
   for (let i = 1; i < heights.length - 1; i++) {
       if (heights[i] >= heights[i - 1] && heights[i] >= heights[i + 1]) {
           peakIndex = i;
           break;
       }
   }
   if (heights[0] >= heights[1]) peakIndex = 0;
   if (heights[heights.length - 1] >= heights[heights.length - 2]) peakIndex = heights.length - 1;
   return peakIndex;
}

Asked in Top Tech Interviews

Microsoft

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.

Sign Up & Solve Free ā†’Browse All Problems