[Google Interview] How To Find The Peak Element In Python?

Company tags: Google, Microsoft, Facebook, Apple, Amazon, Bloomberg, Uber, Quora, Walmart Labs

As reported by various programmers across the globe, this is a frequently asked question in some of the giant organizations including Google. What if this question showed up in your interview aswell! Would you be able to solve it optimally?

Problem Statement

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

A peak element is an element that is strictly greater than its neighbors.

Note: You may imagine that nums[-1] = nums[n] = -∞.

Challenge: Can you write an algorithm that runs in O(log n) time?

Constraints:

1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
nums[i] != nums[i + 1] for all valid i

Examples

Let’s have a look at some examples to improve our understanding of this problem.

Example 1:
Input: nums = [1, 2, 3, 1]
Output: 2
Explanation: 3 is a peak element, and your function should return the index number 2.

Example 2:
Input: nums = [1, 2, 1, 3, 5, 6, 4]
Output: 1 or 5
Explanation: Your function can return either index number 1 or 5 where the peak element is 2 and 6 respectively.

Example 3:
Input: nums = [10, 12, 14, 16, 18]
Output: 4
Explanation: 18 is a peak element, and your function should return the index number 4.

Example 4:
Input: nums = [20, 15, 10, 5]
Output: 0
Explanation: 20 is a peak element, and your function should return the index number 0.

Example 5:
Input: nums = [5, 5, 5]
Output: 0, 1 or 2
Explanation: Your function can return any index as all the elements are the same, and hence every element is a peak element.

Method 1: Using Linear Search

Approach: The simplest approach would be to use linear search in the array to find the peak element. You have to go through every element in the array and check if it is greater than its neighboring elements. If yes, return it. There are few bases that you must consider while solving this problem:

If the array contains only one element, then it will be the peak element.
If the array has numbers in ascending order (Example 3), the peak element will be the last.
If the array contains numbers in descending order (Example 4), the peak element will be the first element.
If all the elements in the array are the same (Example 5), every element will be a peak element.

Soluton: Now, let’s look at the code to solve the problem.

def peak_element(nums):
    n = len(nums)
    if n == 1:
        return 0
    if nums[0] >= nums[1]:
        return 0
    if nums[n - 1] >= nums[n - 2]:
        return n - 1
    for i in range(1, n - 1):
        if nums[i] >= nums[i - 1] and nums[i] >= nums[i + 1]:
            return i

Let’s run this code on our examples:

# Example 1
nums = [1, 2, 3, 1]
print(peak_element(nums))
# 2

# Example 2
nums = [1, 2, 1, 3, 5, 6, 4]
print(peak_element(nums))
# 1

# Example 3
nums = [10, 12, 14, 16, 18]
print(peak_element(nums))
# 4

# Example 4
nums = [20, 15, 10, 5]
print(peak_element(nums))
# 0

# Example 5
nums = [5, 5, 5]
print(peak_element(nums))
# 0

Hurrah! It passed all the test cases.

Complexity Analysis:

Time Complexity: In the worst-case scenario, the method traverses the whole array. Hence the time complexity of this method will be O(n).
Space Complexity: The space complexity of this method is constant, i.e O(1).

Discussion: There is always a scope of improvement. Can you find the peak element in a better complexity than O(n)?

Method 2: Using Binary Search [Optimal Solution]

Approach: In this approach, you have to compare the middle element of the array with its neighboring elements. You will find the peak element on the right side when the right-side neighbor is greater than the middle-element and on the left-side when the left-side neighbor is greater than the middle element. Apply the same method recursively on the greater neighbor element until you find the peak element.

Algorithm:

Initialize the left as 0 and right as len(nums)-1.
Repeat the following steps until left is less than right or till the peak element gets found:
- Initialize the middle element as left+right/ 2 and check if the middle element is the peak element. If yes, return it.
- If nums[mid-1] > nums[mid] then set he right as right = mid – 1
- If nums[mid+1] > nums[mid] then set he left as left = mid + 1

The following diagram represents the working principle of the above algorithm with the help of an example such that the given array is [1,2,1,3,5,6,4]

Solution: Now, let’s look at the code.

def peak_element(nums) :
    n = len(nums)
    left = 0
    right = n - 1
    while left <= right:
        mid = (left + right) // 2
        if (mid == 0 or nums[mid-1] <= nums[mid]) and (mid == n-1 or nums[mid] >= nums[mid+1]):  
            return mid
        if mid == 0 or nums[mid-1] > nums[mid]:  
            right = mid - 1
        else:  
            left = mid + 1

Test Case Analysis: Let’s run this code on our examples:

# Example 1
nums = [1, 2, 3, 1]
print(peak_element(nums))
# 2

# Example 2
nums = [1, 2, 1, 3, 5, 6, 4]
print(peak_element(nums))
# 5

# Example 3
nums = [10, 12, 14, 16, 18]
print(peak_element(nums))
# 4

# Example 4
nums = [20, 15, 10, 5]
print(peak_element(nums))
# 0

# Example 5
nums = [5, 5, 5]
print(peak_element(nums))
# 1

Yeah! It passed all the test cases.

Complexity Analysis:

Time Complexity: In this method, we have used binary search to find the peak element. Hence the time complexity will be O(logn).
Space Complexity: The space complexity of this method remains constant, i.e O(1).

Conclusion

I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.

?Post Credits: Shubham Sayon and Rashi Agarwal

Recommended: Finxter Computer Science Academy

One of the most sought-after skills on Fiverr and Upwork is web scraping. Make no mistake: extracting data programmatically from websites is a critical life skill in today’s world that’s shaped by the web and remote work.
So, do you want to master the art of web scraping using Python’s BeautifulSoup?
If the answer is yes – this course will take you from beginner to expert in Web Scraping.