DEV Community

Tamim Ikbal
Tamim Ikbal

Posted on

Finding the Peak Index in a Mountain Array

#algorithms #dsa

Hello, my friends! Hope you’re all doing great. Today, we’ll solve the problem of finding a Peak Element in a Mountain Array.

Here is my submission on LeetCode.

Leetcode Submission Image

What is a Peak Element?

A peak element in an array is an element that is greater than both of its neighbors. Simply put, if array[i] is the peak, then:

array[i - 1] < array[i] && array[i] > array[i + 1]
Enter fullscreen mode Exit fullscreen mode

To optimize the search, I use Binary Search to maintain efficient time complexity, moving left or right based on the mid value.

  1. Edge Case: If the array length is 1 or less (array.length <= 1), we return the 0 index.
  2. Edge Case: If the first element is greater than the next (array[0] > array[1]), we return 0, since the first index is the peak index.
  3. Edge Case: If the last element is greater than the previous (array[array.length - 1] > array[array.length - 2]), we return array.length - 1, as the last element is the peak.
  4. Now, if array[mid - 1] < array[mid] && array[mid] > array[mid + 1], we return mid, because it's the peak element, being greater than its neighbors.
  5. Else If: array[mid] > array[mid - 1], we move right since array[mid] is greater than the left element, meaning the peak lies to the right.
  6. Else: We move left, as mid is greater than the right element.

Let's Code

I will code in JavaScript to find the peak element and implement Binary Search for an optimized solution.

var findPeakElement = function (nums) { let length = nums.length; if (1 >= length) { return 0; } if (nums[0] > nums[1]) { return 0; } if (nums[length - 1] > nums[length - 2]) { return length - 1; } let left = 1; let right = length - 2; while (left <= right) { let mid = Math.floor((left + right) / 2); if (nums[mid - 1] < nums[mid] && nums[mid] > nums[mid + 1]) { return mid; } else if (nums[mid] > nums[mid - 1]) { left = mid + 1; } else { right = mid - 1; } } return -1; };
Enter fullscreen mode Exit fullscreen mode

Run Some Test:

console.log(findPeakElement([1, 2, 3, 1])); // Index: 2, Element: 3 console.log(findPeakElement([1, 2, 1, 3, 5, 6, 4])); // Index: 5, Element: 6 console.log(findPeakElement([1])); // Index: 0, Element: 1 console.log(findPeakElement([3, 4, 3, 2, 1])); // Index: 1, Element: 4
Enter fullscreen mode Exit fullscreen mode

You can try this problem: Leetcode

Thanks for reading.

Top comments (0)