Peak of Mountain Array - Binary Search / Implicitly Sorted Array

Problems
21

The explanation says that “The peak element is always larger than the next element. Applying the filter of arr[i] > arr[i + 1] we get a boolean array”.
A similar alternative approach could follow the following explanation:
The peak element is always larger than the previous element. Applying the filter of arr[i] > arr[i-1] we get a boolean array. We now search for the first False element.
I did that but for some reason my code fails on test-case [0 10 3 2 1 0]

    # WRITE YOUR BRILLIANT CODE HERE
    start, end, ans = 0, len(arr)-1, -1
    while start<=end:
        mid = (start+end)//2
        if arr[mid] > arr[mid-1]:
            ans = mid
            start = mid+1
        else:
            end = mid-1
    return ans```
22

not a valid case, doesn’t meet problem requirements for what a peak is

23

The problem with this method is when mid is 0, then it’d compare to mid - 1 = -1. In the above case it’s equal, not greater and so it goes into the else path which is incorrect. The assumption should be there is an -1 position that is -inf. We can do that by adding mid == 0 in the if condition.

start, end, ans = 0, len(arr)-1, -1
    while start<=end:
        mid = (start+end)//2
        if mid == 0 or arr[mid] > arr[mid-1]: # mid == 0
            ans = mid
            start = mid+1
        else:
            end = mid-1
    return ans
24

Looks like there are issues with test cases 2-4. For example, for Test #4 it says expected output is 16 but there is no 16 in the array.

25

I don’t see any issues with these test cases. For case #4, the 16 refers to the index of the peak, not the actual value which is 133.

26

l,r = 0, len(arr) - 1
while(l<=r):
mid = (l+r) // 2
if arr[mid] < arr[mid - 1]:
peak = mid - 1
r = mid - 1
else:
l = mid + 1
return peak

#just look for the point which is minimum thant the prev value.

27

Where are we handling the case of the last element being the peak element?

Traceback (most recent call last):
File “solution.py”, line 19, in
res = peak_of_mountain_array(arr)
File “solution.py”, line 9, in peak_of_mountain_array
if arr[mid] > arr[mid + 1]:
IndexError: list index out of range

28

The last element cannot be the peak A[0]<...<A[k-1]<A[k]>A[k+1]>...>A[n-1]

29

def peak_of_mountain_array(arr: List[int]) → int:
# WRITE YOUR BRILLIANT CODE HERE
left, right = 0, len(arr)

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

I love that finding the boundary problem solves a lot of binary search problems!

31

My solution is a little simpler than the given one:

int peak_of_mountain_array(std::vector arr) {
int left = 0, right = arr.size() - 1;
while(left < right) {
const int mid = (left + right)/2;
if (arr[mid] < arr[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}

32

Oops!
int peak_of_mountain_array(std::vector arr) {
int left = 0, right = arr.size() - 1;
while(left < right) {
const int mid = (left + right)/2;
if (arr[mid] < arr[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}

33

int peak_of_mountain_array(std::vector arr) {

int left = 0, right = arr.size() - 1;

while(left < right) {

    const int mid = (left + right)/2;

    if (arr[mid] < arr[mid + 1]) {

        left = mid + 1;

    } else {

        right = mid;

    }

}

return left;

}

34

Clunky and possibly slower, but this is what I came up with before looking at the explanation:

def peak_of_mountain_array(arr: List[int]) -> int:
    left, right = 0, len(arr) - 1
    max = 0
    max_index = -1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] > max:
            if mid > max_index:
                left = mid + 1
            else:
                right = mid - 1
            max_index = mid
            max= arr[max_index]    
        else:
            if mid > max_index:
                right = mid - 1
                left=0
            else:
                left = mid + 1

    return max_index

The idea being that if you’re to the right of the previous max and the current value is less than previous max, the peak is somewhere on your left so you should throw away everything to your right but also check possibly missed search space. I was intentionally trying to avoid looking up array values for some reason, would be interesting to compare this version against algomonster’s version for speed.

35

Without adding -inf my code works.

def peak(numbs):
l, r = 0, len(numbs)-1
peak = -1
while l<r:
mid = (l+r)//2
if numbs[mid] < numbs[mid+1]:
peak = mid+1
l = mid+1
elif numbs[mid] > numbs[mid+1]:
peak = mid
r = mid
return peak

peak([0,1,2,3,2,1,0])

36

Here is my solution:
public static int peakOfMountainArray(List arr) {
// WRITE YOUR BRILLIANT CODE HERE
int left = 0;
int right = arr.size() - 1;
int mid = 0;
while (left <= right) {
mid = left + (right - left) / 2;
if (arr.get(mid) > arr.get(mid + 1)) {
if(arr.get(mid) > arr.get(mid - 1)) {
return mid;
} else {
right = mid - 1;
}
} else {
left = mid + 1;
}
}
return mid;
}

37

Check this out tho… It is no different than canonical binary search, except the target definition. Instead of a static value, target is dynamic - it’s whatever value is greater than both its neighbors. So we can just get by with a small modification:

def peak_of_mountain_array(arr: List[int]) -> int:
    l, r = 1, len(arr) - 2
    while l <= r:
        mid = (l + r) // 2
        a, b, c = arr[mid - 1 : mid + 2]
        if a < b > c:
            return mid
        elif a < b < c:
            l = mid + 1
        else:
            r = mid - 1
    return mid
38

Nice approach

39

Why is right boundary not handled? Is it because we will never reach mid == len(arr) - 1 case because peak cannot be the last element and len(arr) >= 3

40

Why does the explained solution fail with out of index for this test case: 0 3 4 6 7 1 5
Or is my test case wrong?