My accepted O(logN) Python solution


  • -2
    X
    class Solution:
        # @param num, a list of integer
        # @return an integer
        def findPeakElement(self, num):
            if len(num) <= 1:
                return 0
            def peak(num, start, end):
                if end-start == 1:
                    if start == 0 and num[start] > num[end]:
                        return start
                    if end == len(num)-1 and num[end] > num[start]:
                        return end
                else:
                    mid = (end+start)//2
                    if num[mid] > num[mid-1] and num[mid] > num[mid+1]:
                        return mid
                    left = peak(num, start, mid)
                    if left != None:
                        return left
                    right = peak(num, mid, end)
                    if right != None:
                        return right
            return peak(num, 0, len(num)-1)
    

    Just split the array into two halves if array[mid] is not the peak and call the findPeak function on both left and right halves recursively. Remember to include array[mid] as a part of both left and right halves.


  • 1
    S

    I think your solution is still linear. Your recursion relation is

    C(n) = 2 * C(n/2)

    Telescope the above expression: C(n) = 2 * C(n/2) = 4 * C(n/4) = 8 * C(n/8) ... = 2^log(n) * C(1) = n * C(1)


  • 0
    X

    I changed the original code so that it would only call "right = peak(num,mid,ned)" if left = park(num,start,mid) and left == None. But in this case, it's worst case runtime is still O(n) as you stated. Do you have any good idea of a logarithmic solution?


  • 0
    P
    This post is deleted!

  • 0
    D

    If you split the original into half and only do recursion in one half, the time complexity should be O(logN).

    The equation is:
    C(n) = C(n/2) + constant = C(n/4) + 2constant = C(8/n) + 4constant = ... = C(1) + logN * constant
    Thus, O(logN) complexity


Log in to reply
 

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