Domain 2MediumCORE

Find Peak Element

We are given an integer array nums where no two adjacent elements are equal (nums[i] != nums[i+1]). We need to find any index of a peak element, defined as an element strictly greater than its neighbors. Implicitly, the boundaries act like virtual -∞, meaning the first and last elements can be peaks if they are larger than their single existing neighbor.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Binary Search

162. Find Peak Element

Model: qwen3.5:9b
Topics: Array,Binary Search
FAANG asked: 1
Acceptance rate: 44.1%


Problem Breakdown

We are given an integer array nums where no two adjacent elements are equal (nums[i] != nums[i+1]). We need to find any index of a peak element, defined as an element strictly greater than its neighbors. Implicitly, the boundaries act like virtual -∞, meaning the first and last elements can be peaks if they are larger than their single existing neighbor.

Key Constraints & Edge Cases:

  1. Array Length: Minimum length is 1. A single-element array is trivially a peak.
  2. No Adjacent Duplicates: This simplifies logic significantly; we don’t need to handle plateaus (e.g., [3, 3]). We only care about strictly increasing or decreasing slopes locally.
  3. Virtual Boundaries: nums[-1] and nums[n-1] are -∞. This guarantees that a peak must exist within the array because we cannot descend infinitely on both sides without turning up eventually.

Intuition

A naive approach is to iterate through every element, check its neighbors, and return an index if it’s larger than both (or just one neighbor for boundaries). That would be O(N)O(N) time complexity. While correct, the follow-up asks for logarithmic performance (O(log⁡N)O(\log N)), which implies we need a divide-and-conquer strategy like Binary Search.

Why does binary search work here? The array isn’t sorted globally, but it is “locally” monotonic in segments between peaks. If I pick an element mid and find that the right neighbor (nums[mid+1]) is larger than mid, we are on an upward slope. Since the boundary to the far right is -∞, this upward trend must eventually turn downward somewhere to reach a peak (or hit the array end). Therefore, if I’m going up, there must be a peak in the range [mid+1, n-1].

Conversely, if nums[mid] is larger than nums[mid+1], we are on a downward slope. Since the left boundary is -∞, and we just went down from mid, there must be a peak to our left (or at mid). This allows us to discard half of the search space in every iteration.

Approach

I will implement Binary Search with two pointers, left and right. I’ll calculate the middle index mid. The core logic relies on comparing nums[mid] with its right neighbor nums[mid+1]:

  1. If nums[mid] < nums[mid+1], we are ascending. We discard everything to the left of mid + 1 because a peak must exist in the remaining upper half (including potentially beyond). Set left = mid + 1.
  2. Otherwise (nums[mid] > nums[mid+1]), we are descending or at a local maximum relative to the right neighbor. A valid peak exists either at mid or further left. We discard everything strictly greater than mid, so set right = mid. This ensures convergence while keeping potential peaks in consideration.
  3. The loop continues until left == right. At that point, the element at that index satisfies the peak property because one side was discarded due to being “downward” or boundary -∞.

Complexity Analysis

  • Time: O(log⁡N)O(\log N). We halve the search space in each iteration of the binary search loop.
  • Space: O(1)O(1). Only a few integer variables (left, right, mid) are used for tracking indices; no additional data structures like stacks or maps are required.

Solution

def findPeakElement(nums):
    left, right = 0, len(nums) - 1
    
    # Binary search to narrow down the peak index
    while left < right:
        mid = (left + right) // 2
        
        # Compare current element with its right neighbor.
        # If nums[mid] < nums[mid+1], we are on an upward slope, 
        # so a peak must exist in [mid + 1, right].
        if nums[mid] < nums[mid + 1]:
            left = mid + 1
        else:
            # Otherwise (nums[mid] > nums[mid+1]), we are descending.
            # A peak exists at 'mid' or to the left [left, mid].
            right = mid
            
    return left

# Example usage for verification
print(findPeakElement([1, 2, 3, 1]))      # Output: 2 (Value 3)
print(findPeakElement([1, 2, 1, 3, 5, 6, 4])) # Output: 5 or similar peak index

Edge Cases Handled

  • Single Element Array: The loop condition left < right is false immediately (0 == 0). Returns index 0. Correct since the single element has neighbors -∞.
  • Sorted Ascending/Descending Arrays: If strictly ascending, we keep moving right until the last element (nums[n-1] > -∞). If descending, mid is always greater than neighbor, so we move left until index 0. Both valid peaks found correctly.
  • Boundary Peaks: The logic implicitly handles virtual -∞. We never check indices outside [0, n-1], but the comparison with neighbors ensures boundary elements are treated as potential candidates if they beat their single internal neighbor.