**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 1nums = [1, 2, 3, 1] print(peak_element(nums)) # 2 # Example 2nums = [1, 2, 1, 3, 5, 6, 4] print(peak_element(nums)) # 1 # Example 3nums = [10, 12, 14, 16, 18] print(peak_element(nums)) # 4 # Example 4nums = [20, 15, 10, 5] print(peak_element(nums)) # 0 # Example 5nums = [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 1nums = [1, 2, 3, 1] print(peak_element(nums)) # 2 # Example 2nums = [1, 2, 1, 3, 5, 6, 4] print(peak_element(nums)) # 5 # Example 3nums = [10, 12, 14, 16, 18] print(peak_element(nums)) # 4 # Example 4nums = [20, 15, 10, 5] print(peak_element(nums)) # 0 # Example 5nums = [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:is a critical life skill in todayβs world thatβs shaped by the web and remote work.**extracting data programmatically from websites** - 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.