Find Peak Element


  • 0

    Click here to see the full article post


  • 0
    S

    Boring question


  • 0
    L

    what about [1,1,1]


  • 0
    O

    Am I missing something? If the array is sorted, then the last element is a peak element, since array[i] !== array [i+1];

    So, answer would just be array[array.length - 1] if sorted. That would result in basically O(n)


  • 0
    X

    I'm not sure why the binary search is reliable here since elements in array is not sorted. Let's say nums[mid] < noms[mid + 1], based on the binary search algorithm recursive version, we are looking at range (mid + 1, n - 1), but it is possible that there is a peak in range (0, mid) since it's not sorted array. Can someone help on that? Thanks.


  • 0
    S

    The first solution will give a wrong result for: [1, 7, 5, 3, 6, 6, 7, 2, 4, 5, 8], the result should be 10, whereas it is giving 1, because it is returning at 7 > 5 ? true and the result returned is 1. I do not know what's the logic behind the first approach. Why can't the peak be in the end, or the graphs have multiple valleys?


  • 0
    F

    actually, this question is confusing
    we have this condition: num[i] ≠ num[i+1]
    it means that any single element is different than its neighbors - this condition guaranteed that the max value of all the elements is the peak (as its neighbors cannot be the same, but it is already the max)
    so, we can simply find max value(s) and its index, and return. this also gives O(n) time and O(1) space


  • 0
    A

    @fengsi @OSP123 the goal here is to do it in O(log(n)) not in O(n).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.