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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Peak Element

Number: 162

Difficulty: Medium

Paid? No

Companies: Meta, Google, Bloomberg, Microsoft, Amazon, Goldman Sachs, Visa, Uber, TikTok, Flipkart, IXL, Commvault, Oracle, Wix, Apple, Adobe, Snap, Accenture

Problem Description

Given an array of integers, a peak element is defined as an element that is strictly greater than its neighbors. Given that nums[-1] and nums[n] are considered -∞, find any index of a peak element using an algorithm that runs in O(log n) time.

Key Insights

  • Use a binary search strategy to achieve the required O(log n) time complexity.
  • At each step, compare the middle element with its right neighbor to decide which half to search.
  • Due to the -∞ boundaries, there is always at least one peak in the array.

Space and Time Complexity

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

Solution

We use a binary search approach by maintaining two pointers: low and high. We calculate a mid index and check if it is a peak by comparing it with its neighbors. If the element to the right of mid is greater, then a peak must exist in the right half of the array; otherwise, it will be in the left half. This greedy move is valid due to the boundary conditions where the ends are effectively -∞. By continually narrowing the search space, we can efficiently find a peak element.

Code Solutions

# Python solution for Find Peak Element

def findPeakElement(nums):
    # Initialize pointers for binary search
    low, high = 0, len(nums) - 1
    
    # Continue binary search until low meets high
    while low < high:
        mid = (low + high) // 2  # Find the middle index
        
        # If the element at mid is less than its right neighbor,
        # then a peak exists in the right half.
        if nums[mid] < nums[mid + 1]:
            low = mid + 1
        else:
            # Otherwise, a peak exists in the left half,
            # including possibly mid itself.
            high = mid
    # The low pointer eventually points to a peak element.
    return low

# Example usage:
# result = findPeakElement([1,2,3,1])
# print(result)
← Back to All Questions