Unlocking the Peak: A Binary Search Adventure (LeetCode 162)

Hey fellow coders! 👋 Vansh2710 here, ready to dive into another exciting LeetCode challenge. Today, we're tackling Problem 162: Find Peak Element. Don't let the "medium" tag intimidate you; with the right approach, this problem is a fantastic introduction to the power of binary search beyond just sorted arrays. Plus, it has a cool O(log n) time complexity requirement that makes us think smart!

⛰️ What's a Peak Element Anyway?

Imagine you're walking across a mountain range represented by an array of numbers. A "peak element" is simply a point higher than both its immediate neighbors.

More formally:
Given a 0-indexed integer array nums, we need to find an index i such that nums[i] is strictly greater than nums[i-1] AND nums[i] is strictly greater than nums[i+1].

The Super Important Twist:
The problem tells us to imagine that nums[-1] = nums[n] = -∞. This is crucial! It means elements at the very ends of the array are always considered peaks if they're greater than their one actual neighbor. For example, in [3, 2, 1], 3 is a peak because 3 > -∞ (its imagined left neighbor) and 3 > 2. Similarly, in [1, 2, 3], 3 is a peak because 3 > 2 and 3 > -∞ (its imagined right neighbor).

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

• 3 at index 2 is a peak because 3 > 2 and 3 > 1. Output: 2.

Example 2: nums = [1,2,1,3,5,6,4]

• 2 at index 1 is a peak (2 > 1, 2 > 1).
• 6 at index 5 is a peak (6 > 5, 6 > 4). The problem says we can return the index of any peak. So, 1 or 5 would both be valid outputs.

🤔 The "Aha!" Moment - Intuition

The first thought might be, "Just loop through the array and check each element!" This works and would be O(n) time complexity. But wait, the problem explicitly states: "You must write an algorithm that runs in O(log n) time."

This O(log n) constraint is a HUGE hint. What algorithm usually runs in logarithmic time? Binary Search!

But binary search is for sorted arrays, right? Our array nums isn't sorted. So, how can we use it?

The key insight comes from the "imaginary -∞ neighbors" and the guarantee that nums[i] != nums[i+1]. This means there are no plateaus (e.g., [1, 2, 2, 3]), so the array is always either going up or down.

Consider any element nums[mid]:

• If nums[mid] is less than its right neighbor nums[mid + 1]: This means we are on an ascending slope. Since nums[n] = -∞, there must be a peak somewhere to the right of mid (because the numbers eventually have to come back down or hit the "infinity wall" on the right). We can discard mid and everything to its left.
• If nums[mid] is greater than its right neighbor nums[mid + 1]: This means we are either at a descending slope or mid itself is a peak. In either case, a peak must exist at mid or somewhere to its left. We can discard everything to the right of mid + 1.

This structure allows us to eliminate half of the search space in each step, just like a classic binary search!

🚀 Step-by-Step Approach

Let's formalize our binary search strategy:

1. Initialize Pointers:

   • left = 0 (start of the array)
   • right = len(nums) - 1 (end of the array)

2. Loop Condition: Continue as long as left < right. When left == right, we've found our peak!

3. Calculate Mid:

   • mid = left + (right - left) // 2 (This prevents potential integer overflow compared to (left + right) // 2 for very large left and right, though less critical in Python).

4. Decision Time: Compare nums[mid] with nums[mid + 1].

*   **Case 1: `nums[mid] < nums[mid + 1]`**
    *   We're on an uphill climb. The peak *must* be to the right of `mid`.
    *   So, we update `left = mid + 1`.

*   **Case 2: `nums[mid] > nums[mid + 1]`**
    *   We're either on a downhill slope, or `mid` is the peak itself.
    *   A peak *must* exist at `mid` or somewhere to its left.
    *   So, we update `right = mid`. We keep `mid` in the search space because it *could* be the peak.

1. Return: When the loop terminates (left == right), left (or right) will be the index of a peak element. Return left.

This approach cleverly uses the "guaranteed peak" property to steer the binary search, even without a globally sorted array. The nums[-1] = nums[n] = -∞ assumption handles boundary conditions gracefully, ensuring our comparisons are always valid.

💻 The Code

class Solution:
    def findPeakElement(self, nums: list[int]) -> int:
        # Initialize left and right pointers for binary search
        left, right = 0, len(nums) - 1

        # The loop continues as long as there's a range to search
        # When left == right, we've converged on a single element, which must be a peak
        while left < right:
            # Calculate mid-point to avoid potential overflow with (left + right) // 2
            mid = left + (right - left) // 2

            # Compare nums[mid] with its right neighbor nums[mid + 1]
            if nums[mid] < nums[mid + 1]:
                # If nums[mid] is smaller than its right neighbor,
                # we are on an ascending slope.
                # This means a peak MUST exist to the right of 'mid'.
                # So, we discard 'mid' and everything to its left, and search in [mid + 1, right].
                left = mid + 1
            else:
                # If nums[mid] is greater than its right neighbor,
                # we are either on a descending slope, or 'mid' itself is a peak.
                # This means a peak MUST exist at 'mid' or to its left.
                # We keep 'mid' as a potential answer and search in [left, mid].
                right = mid

        # When the loop terminates, left (which is equal to right)
        # will be the index of a peak element.
        return left

⏱️ Complexity Analysis

• Time Complexity: O(log n)

  • This is the beauty of binary search! In each step, we effectively halve the search space. For an array of n elements, this takes log n steps.

• Space Complexity: O(1)

  • We are only using a few constant variables (left, right, mid), regardless of the input array size. No extra data structures are allocated that scale with n.

🚀 Key Takeaways

1. O(log n) often screams Binary Search: Even if the array isn't globally sorted, look for properties that allow you to eliminate half the search space in each step.
2. Leverage Problem Constraints: The nums[-1] = nums[n] = -∞ and nums[i] != nums[i + 1] constraints are critical. They simplify boundary conditions and guarantee the existence of a path towards a peak.
3. Binary Search isn't just for equality: You can use binary search to find ranges, minimums/maximums, or even "turning points" like peaks, by carefully adjusting left and right based on comparisons.
4. "Guaranteed Peak" Logic: The fundamental reason this works is that if you're on an uphill path, a peak must be ahead. If you're on a downhill path (or at a peak), a peak must be at or behind you in that direction.

Hope this breakdown helps you understand how to approach problems like "Find Peak Element" with the power of binary search! Keep coding, keep learning, and I'll see you in the next one!

Authored by Vansh2710. Published on 2026-03-24 18:41:15.