We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Peak Element

Difficulty: Medium

Problem Description

A peak element is an element that is strictly greater than its neighbors. Given a 0-indexed 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. You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

Key Insights

  • A peak can occur at any index where the element is greater than both its neighbors.
  • The problem can be solved using a binary search approach to achieve O(log n) time complexity.
  • The constraints guarantee that there are no equal adjacent elements, ensuring a clear definition of peaks.

Space and Time Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Solution

The solution leverages a binary search algorithm. We start with two pointers, left and right, representing the bounds of the search space. We calculate the middle index and check if the middle element is a peak. If it is not, we determine which side to search next based on the values of the middle element and its neighbors. This process continues until we find a peak.

Code Solutions

def findPeakElement(nums):
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        # Check if mid is a peak
        if nums[mid] > nums[mid + 1]:
            right = mid  # Move left
        else:
            left = mid + 1  # Move right
            
    return left  # or right, both are same here
← Back to All Questions