The problem is not well defined.


  • 3
    L

    The problem should state that there is only one peak in the sequence. Otherwise logarithmic complexity is not possible.

    For example:
    [1,2,1,3,4,5,0] has two peaks: 2 and 5. In such case, the search is O(n).


  • 3
    S

    Yes this is something you definitely should have your interviewer clarify before start answering the question. For this problem, it says "find a peak element", instead of "find the peak element", implying that there could be multiple peak elements and you just need to return the index to one of them.


  • 0

    Actually the array may contain multiple peaks. I have updated the problem statement that clarifies that the input array may contain multiple peaks. In that case return the index to any one of the peaks is fine. I thought this may give out too much hints, oh well..


  • 0
    N

    I agree with you. I was thinking, how can we do that in a logarithmic complexity if input is [↗↘↗↘].


  • 0

    I think the spoiler should be part of the instructions.
    You should also reduce the TLE maybe... I passed the test with a linear algorithm (I hadn't seen the spoiler).


  • 0
    Y

    There could be multiple peaks and logarithm is still possible. The key is this assumption given in the problem: num[-1] == num[n] == -infinity.


Log in to reply
 

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