[LeetCode] Find Peak Element

leetcode

An intuitive way would be just loop through all the elements and check whether it’s a peak element.

Best case: O(1), average case: O(n), worse case: O(n)

1
2
3
4
5
6
7
8
9
10
class Solution:
    """
    @param: A: An integers array.
    @return: return any of peek positions.
    """
    def findPeak(self, A):
        # write your code here
        for i in range(1, len(A)-1):
            if A[i] > A[i-1] and A[i] > A[i+1]:
                return i

However, this will result in TLE (Time Limit Exceeded) for longer inputs.

How can we improve the result? To get a time complexity better than O(n), we should try to reach O(log(n)). When we see log(n), it’s easy to think about binary search.

If we check any point and its right side is increasing, then one peak must exist at the right; on the other hand, if left side is increasing, then one peak must exist at the left. We can use this heuristic to keep lowering the search range and eventually will find a peak.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    """
    @param: A: An integers array.
    @return: return any of peek positions.
    """
    def findPeak(self, A):
        # write your code here
        l = 0
        r = len(A)-1
        m = (r - l)//2
        while l + 1 < r:
            if A[m] > A[m-1] and A[m] > A[m+1]:
                return m
            elif A[m+1] > A[m]: # peak to the right
                l = m
            else: # peak to the left, or both sides
                r = m
            m = (r - l)//2 + l