The problem is not well defined.

  • 3

    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

    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

    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

    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.