Find a peak in a mountain 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

Reframing the question

1. What is a mountain array?
1. A mountain array is an array of length at least 3 elements, strictly increasing from starting till index i, and then strictly decreasing from index i to last index. The end of the arrays can be assumed to be -∞.

2. What is a peak element?
1. A peak element is an element that is strictly greater than both its neighbors.
Copy

nums = [1,2,3,4,3,2,1]
peak = 4 (at index 3)

Intuition

1. We will traverse the array in a linear fashion until we get an element that is greater than the element to its left and right, this is O(N) operation.
Copy

#iterating over the whole array 
	#if nums[i] >= arr[i - 1] and nums[i] >= arr[i + 1]:
			#return i which happens to be the peak.

2. The array is not sorted so we can’t use binary search directly, but as we talked about in ⁉️Thought Experiment, Does an array need to be sorted to run Binary Search? We need to divide the array into separate halves and each half tells a story of where the target is. Can we do that in this case?
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 .

Implementation 0.5

1. Lets code it up? Wait it gave us an error!!!!
Copy

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

            decreasingHalf = nums[mid] > nums[mid + 1]
            
            if decreasingHalf:
                possibleValue = mid
                right = mid - 1
            else:
                left = mid + 1

        return possibleValue

1. Why did it give us an error this gives code doesn’t work on [1,2,3] Why?
2. for two reasons
1. We can't check mid + 1 for the last element to determine which half it belongs to, as it would go out of bounds.

IndexError: list index out of range decreasingHalf = nums[mid] > nums[mid + 1]


2. Not just that, for a question like this we will not even get into the decreasing half. So will not be able to return a possible peak.

3. How do we rectify this?
1. For a strictly ascending array when we are on the last element we end up being out of bounds. And we never end up to a peak in a strictly ascending array.
2. As discussed in the definition of what a mountain array is, since we know that the ends of the arrays can be assumed to be negative infinity we can pad the array with an imaginary node of negative infinity (∞). Which will make 3 at index 2 a peak. Since 3 > 2 and 3 > -inf.

3. For a strictly increasing array, the last element is the peak element.
4. We can modify a few lines of code to ensure we don't exceed the boundaries when we reach the peak of the increasing half. We should also return the last value as the peak.
Copy

lastElement = len(nums) -1
decreasingHalf = mid == lastElement or nums[mid] > nums[mid + 1]

5. You might ask what will happen to a strictly decreasing case. Will we go out of bounds or return the wrong value?

1. Not really. We will return the first True value, or the first value in the decreasing half, which is the peak in this case.
2. When we are on the first value, nums[mid] > nums[mid+1] will not go out of bounds, since we are coming from the right.
3. See it all comes together.

Implementation 1.0

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)

📐Understanding Time Complexity of OLog(N): Math + Intuition