Peak of Mountain Array - Binary Search / Implicitly Sorted Array

Problems
61

why don’t we just compare the element with the left and right side? if it’s bigger than the both sides than it’s the peak element.

here is a simple solution in Kotlin:

fun findPeakElement(nums: IntArray): Int {
     require(nums.size > 3)
    var left = 1 
    var right = nums.size - 2
    
    while (left <= right) {
        val mid = left + (right - left) / 2
        
        // Bigger than the element on the left and right
        if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
            // Found the peak element
            return mid
        } else if (nums[mid] < nums[mid + 1]) {
            // Move right if the mid element is smaller than the next element
            left = mid + 1
        } else {
            // Move left if the mid element is smaller than the previous element
            right = mid - 1
        }
    }
    
    // This should not be reached if there is always a peak
    return -1
}
62

Curious why are we adding mid == alen - 1 as part of the feasible function?

The question states - “Note that the peak element is neither the first nor the last element of the array”

And - mountain array - “has at least 3 elements”

Therefore the peak cannot be the last element alen - 1 in the array.

63

I see to handle a specific sorted array case where the last element is the peak. For example, input array [7 8 9], the mid index can become 2, in which case it acts as boundary check for arr[mid+1] in evaluating the OR condition.

But the Algomonster code editor is generating the correct answer for custom input [7 8 9], even without mid=alen-1 boundary check.

64

The provided solution contains the redundant condition that can be removed. In the context of this problem, checking if mid is the last element (mid == alen - 1 ) is redundant. Since we’re guaranteed that the peak is not at the end, there’s no need to include a condition specifically to handle the end of the array. We could remove the variable, alen, and the redundant condition to simplify the solution as follows:

function peakOfMountainArray(arr) {
  let left = 0;
  let right = arr.length - 1;
  let boundaryIndex = -1;

  while (left <= right) {
    let mid = left + Math.floor((right - left) / 2)

    if (arr[mid] > arr[mid + 1]) {
      boundaryIndex = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return boundaryIndex;
}
65

The JS solution is written differently than all other previous examples for binary search, making the solution hard to follow. Previous binary search tutorials provide a “template” which this solution violates for seemingly no reason.
The mid function is confusingly written like this:

let mid = left + Math.floor((right - left) / 2);

when it should be written like this:

let mid = Math.floor((left+right)/2);

It’s functionally equivalent, but avoids confusingly subtracting the pointer indexes to get the mid point. Just use addition and division and leave subtraction out of it.

Also, the feasibility function confusingly adds a check for being at the END of the array. That is not required, because the description states that the peak explicitly can not be at the start or end of the list.

I would recommend that the explanation function use this code, which passes all test cases and uses the same “template” for binary search found in previous chapters.


function peakOfMountainArray(arr) {   
    let left = 0;
    let right = arr.length -1;
    let boundary_index = -1;
    while(left <= right) {
        let mid = Math.floor((left+right)/2);
        if(arr[mid] > arr[mid+1]){ // if mid>mid+1, than mid is peak!
            boundary_index = mid;
            right = mid-1;
        } else {
            left = mid+1;
        }
    }
    return boundary_index;
}
66

The array strictly increases until the peak element and then strictly decreases. This is the mentioned criteria. So you input is not valid for the test case of this question.

67

good job, i did the same but using a bit complex code this is better.

69

I don’t understand why the below code won’t work as a solution yet its inverse does. I’ve tried really hard to grasp it but it’s just not making sense to me. Can someone explain? The ai bot isn’t helping.

def peak_of_mountain_array(arr: List[int]) → int:
answer = 0
left, right = 0, len(arr) - 1

while left <= right:
    mid = (left + right) // 2
    if arr[mid] > arr[mid - 1] or arr[0]:
        answer = mid
        left = mid + 1
    else:
        right = mid -1
return answer
70

I’m trying to understand that myself