Finding the Peak Index in a Mountain Array

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.

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]

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;
};

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

You can try this problem: Leetcode

Thanks for reading.