Find Peak Element | Leetcode 162 | Graph Binary Search

The “Find Peak Element” problem is a classic question that helps you practice binary search and array manipulation. In this blog, we’ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.

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.

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

Here’s the [Problem Link] to begin with.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Constraints:

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• nums[i] != nums[i + 1] for all valid i.

Brute Force Solution (Linear Scan)

Intuition and Approach

Let’s solve the problem in the most straightforward way:

1. Check Edge Cases:
   • If the array has only one element, it’s a peak.
   • If the first element is greater than the second, it’s a peak.
   • If the last element is greater than the second last, it’s a peak.
2. Scan Each Element:
   For the rest, check if an element is greater than both its neighbors.
3. Why does this work?
   We check every possible peak, so we’re sure to find one.

This approach is easy to understand but not the most efficient for large arrays.

Code Implementation

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        elif nums[0] > nums[1]:
            return 0
        elif nums[n - 1] > nums[n - 2]:
            return n - 1
        for i in range(1, n - 1):
            if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
                return i

Code Explanation

• Handle special cases for arrays of size 1, or if the peak is at the start or end.
• For the rest, check each element (except first and last) to see if it’s a peak.
• Return the index as soon as a peak is found.

Dry Run

Input:
nums = [1][1]

• n = 4
• nums = 1 < nums = 2
• nums = 1 < nums = 3
• i = 1: nums = 2 < nums = 3
• i = 2: nums = 3 > nums = 2 and nums = 3 > nums = 1 → return 2

Final Output:
2

Time and Space Complexity

• Time Complexity: O(n)
  We may have to check every element.
• Space Complexity: O(1)
  Only a variable for looping.

Conclusion

The brute force approach is simple and works for small arrays, but it’s not the best for large inputs.

Optimal Solution (Binary Search)

Intuition and Approach

We can do much better using binary search:

1. Binary Search:
   Use two pointers (low and high) to perform binary search.
2. Check Neighbors:
   • If the middle element is a peak, return it.
   • If the middle element is less than its right neighbor, the peak must be on the right.
   • Otherwise, the peak is on the left.
3. Why does this work?
   If you always move towards the greater neighbor, you are guaranteed to find a peak.

Code Implementation

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        if nums[0] > nums[1]:
            return 0
        elif nums[-1] > nums[-2]:
            return len(nums) - 1
        low = 1
        high = len(nums) - 2
        while low <= high:
            mid = (low + high) // 2
            if nums[mid] > nums[mid - 1] and nums[mid] > nums[mid + 1]:
                return mid
            if nums[mid] > nums[mid + 1]:
                high = mid - 1
            else:
                low = mid + 1

Code Explanation

• Handle special cases for arrays of size 1, or if the peak is at the start or end.
• Use binary search between indices 1 and n-2.
• If the mid element is a peak, return its index.
• If the mid element is greater than its right neighbor, move left.
• Otherwise, move right.

Dry Run

Input:
nums = [1][1]

• len(nums) = 4
• nums = 1 < nums = 2
• nums = 1 < nums = 3
• low = 1, high = 2
• mid = (1+2)//2 = 1
• nums = 2 < nums = 3 → move right, low = 2
• mid = 2
• nums = 3 > nums = 2 and nums = 3 > nums = 1 → return 2

Final Output:
2

Time and Space Complexity

• Time Complexity: O(log n)
  Binary search divides the array each time.
• Space Complexity: O(1)
  Only a few pointers.

Conclusion

The optimal solution is efficient and works well for large arrays. It’s the best approach for interviews and practical use.

Final Thoughts

The “Find Peak Element” problem is a great example of how to optimize from brute force to an efficient binary search solution. Start with brute force to understand the basics, then use binary search for best performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.