Algorithms for Coding Interviews in Python/

...

/

Solution: Find the Peak Element

Solution: Find the Peak Element

This review discusses the solution of the peak element challenge in detail.

We'll cover the following...

Solution: 1

One simple way to solve this problem is:

Python 3.5
# Function to find the peak element in the list
def find_peak(lst):
    """
    Finds a peak element
    :param lst: List of integers
    :return: Returns a peak element in a given list
    """
    # If the list in empty
    if len(lst) is 0:
        return -1
    
    # If the list has only one element
    if len(lst) is 1:
        return lst[0]
    for i in range(1, len(lst) -1):
        if lst[i] >= lst[i-1] and lst[i] >= lst[i+1]:
            return lst[i]
    if lst[0] >= lst[1]:
        return lst[0]
    elif lst[len(lst) - 1] >= lst[len(lst) - 2]:
        return lst[len(lst) - 1]
    return -1
# Driver code to test above function
if __name__ == '__main__':
    # Example: 1
    lst = [7, 11, 22, 13, 4, 0]
    print('One peak point is: ', find_peak(lst))
    # Example: 2
    lst = [0, 3, 100, 2, -1, 0]
    print('One peak point is: ', find_peak(lst))
    # Example: 3
    lst = [6, 5, 4, 3, 2, 1]
    print('One peak point is: ', find_peak(lst))

Explanation

  1. Start from the beginning, compare each element with its neighbors
  2. Return the peak element wherever you find it in the list

If the list is sorted in an increasing order with no repetition, then the last element is always a peak element:

In this case, the peak element is at the end of the list.

Time complexity

This solution gives us a worst-case time complexity of O(n)O(n).

Any better solution?

Solution: 2 (efficient)

Using divide and conquer, we can speed up the whole process. Have a look at the solution given below:

Python 3.5
# Utility function
def find_peak_recursive(low, high, lst):
    """
    Finds a peak element
    :param low: Starting index of a given list
    :param high: Ending index of a given list
    :param lst: List of integers
    :return: Returns a peak element in a given list
    """
    # Finding the middle index
    middle = low + (high - low) // 2
    # If there are neighbours
    if (middle == len(lst) - 1 or lst[middle + 1] <= lst[middle]) and (middle == 0 or lst[middle - 1] <= lst[middle]):
        return middle
    # If left neighbour is greater, then peak element is in the left half
    elif (lst[middle - 1] > lst[middle]) and middle > 0:
        return find_peak_recursive(low, (middle - 1), lst)
    # If right neighbour is greater, then peak element is in the right half
    else:
        return find_peak_recursive((middle + 1), high, lst)
def find_peak(lst):
    """
    Finds a peak element
    :param lst: List of integers
    :return: Returns a peak element in a given list
    """
    return lst[find_peak_recursive(0, len(lst) - 1, lst)]
# Driver code to test above function
if __name__ == '__main__':
    # Example: 1
    lst = [7, 11, 22, 13, 4, 0]
    print('One peak point is: ', find_peak(lst))
    # Example: 2
    lst = [0, 3, 100, 2, -1, 0]
    print('One peak point is: ', find_peak(lst))
    # Example: 3
    lst = [6, 5, 4, 3, 2, 1]
    print('One peak point is: ', find_peak(lst))

Explanation

Start with the middle element of the list Line 11

  • Compare the element with its neighbors
    • If the middle element is not smaller than any of its neighbors, we return it Line 14
    • If the middle element is smaller than its left neighbor, there is always a peak in the left half Line 18
    • If the middle element is smaller than its right neighbor, there is always a peak in the right half Line 23
...