algoadvance

The problem is from LeetCode (162. Find Peak Element):

A peak element is an element that is strictly greater than its neighbors.

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.

You may imagine that nums[-1] = -∞ and nums[n] = -∞, which means that an element is always considered to be strictly greater than a neighbor that is out of bounds.

You must write an algorithm that runs in O(log n) time.

Clarifying Questions

  1. Q: What should we do if the array has multiple peak elements? A: Return the index of any one of the peak elements.

  2. Q: Can the array have duplicate values? A: The problem implies that we deal with strictly greater neighbors, so the assumption would be no duplicates in direct neighbors.

  3. Q: What is the minimum length of the array? A: The array must contain at least one element.

Strategy

To meet the O(log n) time complexity requirement, a binary search approach is appropriate. Here’s a step-by-step strategy:

  1. Binary Search Approach:
    • Initialize two pointers, left at the start of the array and right at the end of the array.
    • Calculate the middle index mid.
    • Compare the middle element nums[mid] with its neighbors nums[mid - 1] and nums[mid + 1] (handling the edge cases where mid is at the boundaries of the array).
    • If nums[mid] is greater than both of its neighbors, nums[mid] is a peak element, return mid.
    • If nums[mid] is less than its right neighbor nums[mid + 1], there must be a peak element to the right. Move the left pointer to mid + 1.
    • If nums[mid] is less than its left neighbor nums[mid - 1], there must be a peak element to the left. Move the right pointer to mid - 1.
    • Continue the process until left equals right, at which point you’ve found a peak element.

Code

def findPeakElement(nums):
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = (left + right) // 2
        
        if nums[mid] > nums[mid + 1]: 
            # Peak must be in the left half or at mid
            right = mid
        else:
            # Peak must be in the right half
            left = mid + 1
    
    return left

# Example usage:
print(findPeakElement([1,2,3,1]))  # Output: 2 (index 2, value 3, is a peak)
print(findPeakElement([1,2,1,3,5,6,4]))  # Output: 1 (could also be 5)

Time Complexity

Feel free to ask if you have any further questions or need additional explanations!

Try our interview co-pilot at AlgoAdvance.com