Find Peak Element in a mountain range array.

Prerequisites: 🍦Binary Search(Vanilla) , 🔑Find the First True in a Sorted Boolean Array , ⁉️Thought Experiment, Does an array need to be sorted to run Binary Search?

Question

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Reframing the Question

1. What is a mountain range array?
1. Similar to a mountain array in ⛰️Find a peak in a mountain array. A mountain range array is an array with multiple mountain arrays and multiple peaks.
2. Solving for a mountain array as we did in ⛰️Find a peak in a mountain array.
1. We can split the array into two halves: an increasing half and a decreasing half. These two halves tell us a story about where the target is.

2. We know we are in the increasing half if the value next to our current midpoint is greater than the midpoint itself, in that case the peak will be to the right.
1. if nums[mid - 1] < nums[mid] , the peak will be to the right.

3. We know we are in the decreasing half if the value before our current midpoint is less than the midpoint itself, in that case, the peak will be to the left
1. If nums[mid]< nums[mid + 1], the peak will be to the left.

4. We can add the peak to either half of the binary search since it reduces to the edge of either half. If we add it to the decreasing half, the first element will be the peak also the edge of that half. This should sound familiar.
1. The problem is reduced to finding the 🔑Find the First True in a Sorted Boolean Array .


2. In a mountain range array, there can be multiple mountains and thus multiple peaks, let's visualize what it looks like.


3. Returning the first value in either half seems implausible as we have multiple increasing and decreasing halves so we can’t frame the problem to 🔑Find the First True in a Sorted Boolean Array as we are not able to get a sorted boolean array after implementing the True Criteria.

4. If I told you we can use the same solution we used in ⛰️Find a peak in a mountain array. Will that surprise you? I know it is counterintuitive, but the outcome might surprise you!
1. Increasing Half (ignore the True False values for now)
1. Step 1

2. Step 2: We are increasing in the second half, so the peak will be on the right side. Therefore, let's remove all the elements to the left, as the peak cannot be there.

3. Step 3: The problem is reduced to a mountain array.

2. What if we are on a decreasing half? The problem reduces to finding a mountain array. The same process applies to the increasing half, with one small difference: we would store the midpoint as a possible value.
1. We will not store the midpoint with the increasing half, as the value after the midpoint has more chances of being a peak than the midpoint itself, and if it is edge we will simply return that as possible Min


3. The midpoint will fall on either false or true. It will keep reducing the mountain range array to a single mountain array until the search has gone over all the possible elements, at which point it will return a possible value. Both strictly ascending and descending mountain ranges will be covered.
4. So we can use the Solution in ⛰️Find a peak in a mountain array. And will work for this question, you can try it for yourself.

Implementation

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        
        left, right = 0, len(nums) - 1
        possibleValue = -1

        while left <= right:
            mid = left + (right - left) // 2

            lastElement = len(nums) -1
            decreasingHalf = mid == lastElement or nums[mid] > nums[mid + 1]
            
            if decreasingHalf:
                possibleValue = mid
                right = mid - 1
            else:
                left = mid + 1

        return possibleValue

Sandbox—PythonTutor (Visualized)

Complexities

Time Complexity: O(log(n))

Space Complexity: O(1)