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

Rate this post

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.

## 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:

1. If the array contains only one element, then it will be the peak element.
2. If the array has numbers in ascending order (Example 3), the peak element will be the last.
3. If the array contains numbers in descending order (Example 4), the peak element will be the first element.
4. 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 >= nums:
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:

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:

1. Initialize the left as` 0` and right as `len(nums)-1`.
2. 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:

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