Peak of Mountain Array - Binary Search / Implicitly Sorted Array

Problems
41 
int n = arr.size() - 1;
while(arr[n] < arr[n-1] && n > 0) {
    n -= 1;
}
return n;
42

This test case contains two peaks, 7 at index 4 and 5 at index 6. This isn’t a valid test case!

43

Curtesy of Wizardinho, find me on Leet Code :clown_face:

function peakOfMountainArray(arr) {
// WRITE YOUR BRILLIANT CODE HERE
let left=0;
let right=arr.length-1;

while(left<=right){
    const mid = Math.floor((left+right)/2);
    let peak = arr[mid];
    
    if(peak>arr[mid-1] && peak>arr[mid+1]) return mid;
    else if(peak<arr[mid+1]) left=mid+1;
    else right=mid-1;
}
return 0;

}

44

My solution, thoughts?
def peak_of_mountain_array(arr: List[int]) → int:
# WRITE YOUR BRILLIANT CODE HERE
left, right = 0, len(arr) - 1

while left <= right:
    mid = (left + right) //2
    
    if arr[mid] > arr[mid - 1]  arr[mid] > arr[mid + 1]:
        return mid
    elif arr[mid] < arr[mid + 1]:
        left = mid + 1
    else:
        right = mid - 1
45

small typo,
the if condition is missing “and”
if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid + 1]:

46

My thoughts also

47

My solution, if we use “right = mid” instead then our while loop will be “while left < right” instead of less than or equal to. This works well for us because it takes care of the edge case when we reach the ends of the list, eliminating the need for the condition “if mid == len(arr)-1”
left, right = 0, len(arr)-1
while left < right:
mid = left + (right-left) // 2
if arr[mid] > arr[mid+1]:
right = mid
else:
left = mid + 1
return left

48

uhh reformatting solution:
left, right = 0, len(arr)-1
while left < right:
mid = left + (right-left) // 2
if arr[mid] > arr[mid+1]:
right = mid
else:
left = mid + 1
return left

49

It’s seems like it’s working. Will it work in every situation.
let min = 0, max = arr.length - 1,index = -1;
while (min <= max){
const mid = min + Math.floor( (max -min)/2 );
if (arr[mid-1] < arr[mid]){
index = mid;
min = mid+1;
}else max = mid -1;
}
return index;

50

If the elements monotonically increase (Always increasing or REMINAING CONSTANT, and never decreasing) in contrast with STRICTLY increasing, then you CANNOT reliably use binary search to solve this. For example, [2 4 2 2 2 2] is a valid input but given that is monotonically increase [2 4] and monotonically decreases [4 2 2 2 2]. If there is a sequence of repeating numbers, you don’t know which way to go with binary search and it’s a 50/50 chance that you go the right direction.

51

yes, it has to be strictly increasing

52

yes, peak cannot be the first or last element

53

“strictly” not “strickly”

54

Why we need condition mid == alen-1?
It works the same way just with if (arr.get(mid) > arr.get(mid + 1))

1 Like
55

Hi,
The description clearly says: “Note that the peak element is neither the first nor the last element of the array.” Given this, below is proposed solution where we first handle edge case where if array length is <=2, we can simply return -1 as neither first or last can be peak according to description. And then, since we know now array length would be at least 3, start our search range from index 1 to 2nd last index. Proposed python solution is as below & it passes all tests. Can you help check if below is good?
On sidenote: I had trouble understanding reference solution condition " mid == alen - 1" & in below proposed solution, I think it will not be needed and hence seems cleaner. Thoughts?

def peak_of_mountain_array(arr: List[int]) → int:
# WRITE YOUR BRILLIANT CODE HERE
N= len(arr)
if N<=2:
return -1 #peak elem is neither the first nor the last elem
#Now,we know array has at least 3 elems
lo=1# because prob says:0th cant be peak
hi=N-2 #because prob says: last cant be peak
cur_boundary=-1

while(lo<=hi):
    mid = lo + (hi-lo)//2
    if(arr[mid+1] < arr[mid]):
        cur_boundary = mid
        hi=mid-1
    else:
        lo=mid+1
        
return cur_boundary
2 Likes
56

Do we need the case where mid == alen - 1? The problem states “the peak element is [not] … the last element of the array”, and we would look to the left at mid == alen - 2 (i.e. the second to last element). So is there any case where we’d look at the last element of the array?

2 Likes
57

why are we doing this ```
if mid == alen - 1

58

I have an alternate Java solution which is the inverse, where I looked at arr[i] > arr[i - 1]. Instead of the padded element at the end, I had to make up for the 0th element, which we know is never the peak.

  public static int peakOfMountainArray(List<Integer> arr) {
    int peakIdx = -1;
    int left = 0;
    int right = arr.size() - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (mid == 0 || arr.get(mid) > arr.get(mid - 1)) {
        peakIdx = mid;
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return peakIdx;
  }
59

+1, because the Java solution passes the test cases without this check, i.e. Updating the code to this still works:

            int mid = left + (right - left) / 2;
            if (/*mid == alen-1 ||*/ arr.get(mid) > arr.get(mid + 1)) { /* etc */

I could be wrong, but it doesn’t seem possible to search an array [..., n-2, n-1] where mid = n-1?

60

Simple crisp solution in JAVA.

public static int peakOfMountainArray(List arr) {
int left = 0;
int right = arr.size() - 1;
int n = arr.size();

    while (left <= right) {
        
        int mid = left + (right - left) / 2;
        
        // check if mid is greater than its immediate neighbors
        if(mid + 1 < n && mid - 1 >= 0 && arr.get(mid) > arr.get(mid + 1) && arr.get(mid) > arr.get(mid - 1)){
            
            return mid;
        }
        
        // check if mid is less than or equals to immediate rightmost neighbor
        if (mid < n - 1 && arr.get(mid) <= arr.get(mid + 1)) {
            
            left = mid + 1;
           
        } else {
            
            right = mid - 1;
        }
    }
    return -1;
    
}

Awaiting any sort of criticisms.