#162

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find Peak Element

Find Peak Element leverages binary search for efficiently locating a peak in an array, a problem commonly asked in technical interviews.

array binary search

Problem Statement

You are given a 0-indexed integer array nums. A peak element is an element that is strictly greater than its neighbors. If nums[-1] and nums[n] are imagined to be -∞, then an element at the edge is also considered a peak if it is larger than its one neighbor. Your task is to find any peak element and return its index.

The array can have multiple peaks. In that case, returning the index of any peak is considered correct. The input guarantees that nums[i] != nums[i + 1] for all valid i, which ensures there is at least one peak. Your solution must run efficiently with binary search over the valid answer space.

Examples

Example 1

Input: nums = [1,2,3,1]

Output: 2

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

Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Constraints

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

Solution Approach

Binary Search over the Array

Apply binary search to the array, where the mid element is compared with its neighbors. Depending on whether the element at mid is larger or smaller than its neighbors, adjust the search space to find the peak.

Edge Case Handling

Consider edge cases, especially with peak elements at the start or end of the array. These cases are handled naturally by the binary search approach as the array's virtual boundaries are treated as -∞.

Time and Space Complexity Optimization

The binary search approach ensures that the solution runs in O(log n) time, and with O(1) space complexity. This is a significant optimization compared to a brute-force approach, which would require O(n) time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The binary search approach reduces the time complexity to O(log n) by halving the search space with each iteration. The space complexity is O(1) since the solution only requires a few variables for tracking indices.

What Interviewers Usually Probe

Assessing the candidate's understanding of binary search and its application to specific problems.
Looking for clarity in explaining why binary search works for this problem, especially with edge cases.
Evaluating the candidate's ability to write efficient, optimal code without unnecessary operations.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the concept of a peak at the edges of the array, especially when dealing with virtual boundaries (-∞).
Forgetting to check both neighbors during the binary search, potentially missing the peak element.
Using a brute-force approach that results in higher time complexity instead of utilizing binary search.

Follow-up variants

Modify the problem to return all peak elements instead of just one.
Extend the problem to find the global peak that is strictly larger than all elements in the array.
Test variations on arrays with repeated elements and adapt the peak definition accordingly.

FAQ

What is the best approach for solving Find Peak Element?

The best approach is using binary search over the valid answer space, which ensures that the solution is both time-efficient and space-efficient.

How does binary search help in the Find Peak Element problem?

Binary search helps by narrowing down the search space to find a peak element in O(log n) time, compared to a brute force approach that would take O(n) time.

Can Find Peak Element have multiple correct answers?

Yes, there can be multiple peaks in the array, and the solution can return any index corresponding to a peak element.

What is the time complexity of the optimal solution for Find Peak Element?

The time complexity of the optimal binary search solution is O(log n), which is much faster than a linear scan of the array.

How does GhostInterview assist with the Find Peak Element problem?

GhostInterview helps by providing practice problems, feedback on binary search techniques, and tips on optimizing solutions for problems like Find Peak Element.

terminal

Solution

Solution 1: Binary Search

We define the left boundary of binary search as $left=0$ and the right boundary as $right=n-1$, where $n$ is the length of the array. In each step of binary search, we find the middle element $mid$ of the current interval, and compare the values of $mid$ and its right neighbor $mid+1$:

1

2

3

4

5

6

7

8

9

10

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            if nums[mid] > nums[mid + 1]:
                right = mid
            else:
                left = mid + 1
        return left

Continue Practicing

#167 two sum ii input array is sorted #154 find minimum in rotated sorted array ii #153 find minimum in rotated sorted array