The “Find Peak Element” problem is a classic question that helps you practice binary search and array manipulation. In this blog, we\u2019ll 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.<\/p>\n\n\n\n
A peak element is an element that is strictly greater than its neighbors.<\/p>\n\n\n\n
Given a 0-indexed<\/strong> integer array You may imagine that You must write an algorithm that runs in Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n Example 1:<\/strong><\/p>\n\n\n\n Example 2:<\/strong><\/p>\n\n\n\n Constraints:<\/strong><\/p>\n\n\n\n Let\u2019s solve the problem in the most straightforward way:<\/p>\n\n\n\n This approach is easy to understand but not the most efficient for large arrays.<\/p>\n\n\n\nnums<\/code>, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks<\/strong>.<\/p>\n\n\n\nnums[-1] = nums[n] = -\u221e<\/code>. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.<\/p>\n\n\n\nO(log n)<\/code> time.<\/p>\n\n\n\nInput:<\/strong> nums = [1,2,3,1]\nOutput:<\/strong> 2\nExplanation:<\/strong> 3 is a peak element and your function should return the index number 2.<\/pre>\n\n\n\n
Input:<\/strong> nums = [1,2,1,3,5,6,4]\nOutput:<\/strong> 5\nExplanation:<\/strong> Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.<\/pre>\n\n\n\n
\n
1 <= nums.length <= 1000<\/code><\/li>\n\n\n\n-231<\/sup> <= nums[i] <= 231<\/sup> - 1<\/code><\/li>\n\n\n\nnums[i] != nums[i + 1]<\/code> for all valid i<\/code>.<\/li>\n<\/ul>\n\n\n
\n\n\n\nBrute Force Solution (Linear Scan)<\/h2>\n\n\n\n
Intuition and Approach<\/h3>\n\n\n\n
\n
\n
For the rest, check if an element is greater than both its neighbors.<\/li>\n\n\n\n
We check every possible peak, so we\u2019re sure to find one.<\/li>\n<\/ol>\n\n\n\nCode Implementation<\/h3>\n\n\n\n