4. Find a Peak Element

A peak element is an element that is greater than its neighbors. Here's the problem presented by the interviewer:

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks; in that case, returning the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞. For example, in array[1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

Define the Problem

The problem has been explained fairly well by the interviewer, but we're going to have Jonathan clear up any doubts or assumptions.

Jonathan: I'll be using JavaScript to solve the problem.

Interviewer: Okay.

Jonathan takes a moment to think, and then says:

Jonathan: I'm also thinking that there are different solutions based on whether the array is sorted or unsorted. Should I solve for both?

Interviewer: Yes, please.

---

Think

Jonathan thinks about the problem for a bit. He's already starting to come up with some solutions and writes out some of his thoughts on the board. Here's his pseudocode:

// Unsorted Array Solution - Linear Search
/* Since we just need to find a single peak element, we can just return the first one we find. Therefore,
   we can just loop through all of the elements once and return the first that is a peak.
   // Within loop, only need to check the next greatest element, since the previous one is going to be
   checked in the prior iteration for being larger.
   // If no element is found, return the array

// Sorted Array Solution - Binary Search
// If array is sorted, we can use the efficient Binary Search algorithm to get a peak element.

---

Write Code and Syntax

Now that the hard part is done, Jonathan just needs to write out the syntax to fill in the pseudocode. As Jonathan writes the code, he explains the syntax.

// Unsorted Array Solution - Linear Search
/* Since we just need to find a single peak element, we can just return the first one we find. Therefore,
   we can just loop through all of the elements once and return the first that is a peak.
   function peakElement(nums) {
      for (int i = 0; i < nums.length - 1; i++) {
      // Within loop, only need to check the next greatest element, since the previous one is going to be
      checked in the prior iteration for being larger.
         if (nums[i] > nums[i + 1])
           return i;
      }
      // If no element is found, return the array
      return nums.length - 1;
   }
// Sorted Array Solution - Last element
// If array is sorted, we would just get the last element in the array as a peak element
   nums[nums.length - 1];

Jonathan: If the array is unsorted, we would need to do a linear search. Since we just need to return a single peak element, we would just return the first peak we find. We don't have to worry about array\[i-1\], since the previous element is going to be checked in the previous iteration in the loop. In a sorted array, we can just return the last element, since we're just looking for a peak and since array\[i\] !== array\[i-1\], the last element is guaranteed to be a peak.