Find Peak Element LeetCode Solution | Code in C++/Java/Python
Problem Description:
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.
Examples:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element, and your function should return the index number 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
- -2³¹ <= nums[i] <= 2³¹ - 1
- nums[i] != nums[i+1] for all valid i
A peak element in array is the index of an element that is greater than its two immediate neighbours. Given an array nums, we are supposed to return the peak element in an array nums.
For now, let's set aside the requirement to solve the problem in O(logn) time complexity and focus solely on the core problem itself.
Brute Force Approach
Intuition:
The first thought that comes to mind for solving this problem is simple: why not check every element in the array one by one and see if it satisfies the condition of being a peak? This idea feels natural because the problem itself defines a peak element in an array as the element that is strictly greater than its neighbours. So, all we need to do is test this condition for each element.
Find Peak Element LeetCode Solution
Think of it this way: for every position in the array (except the indices 0 and n-1, which we handle separately), we compare the element to its immediate neighbours—the one before and the one after. If the current element is greater than both of them, it must be the peak element in the array.
This approach feels intuitive because it directly addresses the problem’s definition. We systematically move through the array, looking at every element and its neighbours. If we find an element larger than both neighbours, we know it satisfies the condition of being a peak. If not, we will continue to the next one.
The reasoning is simple:
- If an element has smaller neighbours, it is a peak by definition.
- By checking every single element, we are guaranteed to find at least one peak because the problem assures us that a peak will always exist (remember, the elements outside the array are considered ∞, so the first and last elements could also be peaks).
This approach makes sense because it’s straightforward and leaves no room for error—we check every possibility. However, while it guarantees a solution, it’s not the most efficient way to solve the problem, as it involves examining each element individually.
By using this approach, we rely purely on the brute force method, where the goal is to explore all options to find the answer. It’s like systematically opening every door in a row of rooms to find the one you’re looking for—it works, but there might be a quicker way!
Dry run
Input: nums = [1, 2, 3, 4, 5]
Output: 4
Explanation: 5 is the peak element and the index of element 5 is 4 so we return 4
Initialization:
- n = 5
Iteration 1: i = 0
- nums[0] = 1
- Check if nums[0] > nums[1] (i.e., 1 > 2), which is false.
- continue to the next iteration.
Iteration 2: i = 1
- nums[1] = 2
- Check if nums[1] > nums[0] and nums[1] > nums[2] (i.e., `2 > 1 and 2 > 3), which is false.
- continue to the next iteration.
Iteration 3: i = 2
- nums[2] = 3
- Check if nums[2] > nums[1] and nums[2] > nums[3] (i.e., 3 > 2 and 3 > 4), which is false.
- continue to the next iteration.
Iteration 4: i = 3
- nums[3] = 4
- Check if nums[3] > nums[2] and nums[3] > nums[4] (i.e., 4 > 3 and 4 > 5), which is false.
- continue to the next iteration.
Iteration 5: i = 4
- nums[4] = 5
- Check if nums[4] > nums[3] (i.e., 5 > 4), which is true.
- Since i is the last element, the condition if (i == n-1) is true, and we return i = 4.
Output:
The function returns 4 because nums[4] = 5 is greater than its only neighbour nums[3] = 4.
Final Output: 4
Steps to write code
Step 1: Edge Case Handling:
- Check if there is only one element. If so, the only element is a peak, so we return 0 (its index).
Step 2: Loop Through the Array:
- The loop runs from the first element to the last element.
Step 3: Check the First Element:
- If i == 0, check if the first element is greater than its next neighbour.
- If true, return i (the index of the peak element).
Step 4: Check the Last Element:
- If i == n - 1, check if the last element is greater than the previous neighbour.
- If true, return i.
Step 5: Check the Middle Elements:
- For all other elements, check if the element is greater than both its previous and next neighbours.
- If true, return i.
Step 6: Return arbitrary value at the end (function will never reach here)
Brute Force in All Languages
find peak element in array code in C++
class Solution {
public:
// Function to find the index of a peak element
int findPeakElement(vector<int>& nums) {
// Get the size of the array
int n = nums.size();
// If there's only one element, it's the peak
if (n == 1) return 0;
// Iterate through the elements of the array
for (int i = 0; i < n; ++i) {
// Check the first element
if (i == 0) {
// If the first element is greater than the second, it's a peak
if (nums[i] > nums[i + 1]) return i;
continue;
}
// Check the last element
if (i == n - 1) {
// If the last element is greater than the second last, it's a peak
if (nums[i] > nums[i - 1]) return i;
continue;
}
// Check the middle elements
if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) return i;
}
// Return -1 if no peak is found (not expected in a valid peak problem)
return -1;
}
};find peak element in array code in JAVA
public class Solution {
// Function to find the index of a peak element
public int findPeakElement(int[] nums) {
// Get the size of the array
int n = nums.length;
// If there's only one element, it's the peak
if (n == 1) return 0;
// Iterate through the elements of the array
for (int i = 0; i < n; ++i) {
// Check the first element
if (i == 0) {
// If the first element is greater than the second, it's a peak
if (nums[i] > nums[i + 1]) return i;
continue;
}
// Check the last element
if (i == n - 1) {
// If the last element is greater than the second last, it's a peak
if (nums[i] > nums[i - 1]) return i;
continue;
}
// Check the middle elements
if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) return i;
}
// Return -1 if no peak is found (not expected in a valid peak problem)
return -1;
}
}find peak element in array code in Python
class Solution:
# Function to find the index of a peak element
def findPeakElement(self, nums: list[int]) -> int:
# Get the size of the array
n = len(nums)
# If there's only one element, it's the peak
if n == 1:
return 0
# Iterate through the elements of the array
for i in range(n):
# Check the first element
if i == 0:
# If the first element is greater than the second, it's a peak
if nums[i] > nums[i + 1]:
return i
continue
# Check the last element
if i == n - 1:
# If the last element is greater than the second last, it's a peak
if nums[i] > nums[i - 1]:
return i
continue
# Check the middle elements
if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
return i
# Return -1 if no peak is found (not expected in a valid peak problem)
return -1find peak element in array code in Javascript
/**
* @param {number[]} nums
* @return {number}
*/
var findPeakElement = function(nums) {
// Get the size of the array
const n = nums.length;
// If there's only one element, it's the peak
if (n === 1) return 0;
// Iterate through the elements of the array
for (let i = 0; i < n; i++) {
// Check the first element
if (i === 0) {
// If the first element is greater than the second, it's a peak
if (nums[i] > nums[i + 1]) return i;
continue;
}
// Check the last element
if (i === n - 1) {
// If the last element is greater than the second last, it's a peak
if (nums[i] > nums[i - 1]) return i;
continue;
}
// Check the middle elements
if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) return i;
}
// Return -1 if no peak is found (not expected in a valid peak problem)
return -1;
};Complexity Analysis of Find Peak Element LeetCode Solution
Time Complexity: O(n)
- Initialization:
int n = nums.size(); takes O(1) time to get the size of the input array nums.
- Edge Case Check (Single Element):
if (n == 1) return 0; is a constant-time check, which takes O(1) time. This is an early exit for arrays with a single element.
- Loop through the Array:
The for loop: for (int i = 0; i < n; ++i) runs from index 0 to n-1. The total number of iterations is n, so the loop itself takes O(n) time.
- Inside the Loop (Conditions):
The conditions inside the loop (for checking the first, middle, and last elements) are simple comparisons, and each comparison operation (nums[i] > nums[i-1], nums[i] > nums[i+1], etc.) takes O(1) time.
There are no nested loops or recursive calls inside the loop, so each iteration consists of constant-time operations.
- Return Statements:
If a peak is found at any index, the function returns immediately with O(1) time complexity.
The loop is terminated early if a peak is found, but this doesn't change the overall worst-case time complexity. In the worst case, the loop will run through all n elements.
- Final Return (-1):
If no peak is found, the function returns -1 at the end, which is a constant-time operation, O(1).
The Overall Time Complexity of the code is O(n)
Space Complexity: O(1)
Auxiliary Space Complexity:
Auxiliary space refers to the extra space used by the algorithm beyond the input data. This includes space for variables, data structures, or recursive calls.
- In this code, the only extra space used is for:
- The variable n (which stores the size of the array), is a single integer and takes O(1) space.
- The loop iterator i, which is another integer and takes O(1) space.
- There are no additional data structures used (like arrays, lists, or stacks) to store intermediate results or perform complex operations.
So, the auxiliary space complexity is O(1) because the algorithm only uses a constant amount of space.
Total Space Complexity:
Since the input array nums takes O(n) space, and the auxiliary space is O(1), the total space complexity is dominated by the input space.
Thus, the total space complexity is O(n).
Is the brute force approach efficient?
In the brute force approach, we found the peak element by simply iterating over the array and checking the peak condition. This approach takes O(n) time which comfortably meets the given constraints.
The n goes up to 1000 only. But O(n) is optimal and works efficiently even with large input sizes like n = 10⁴. Without risking the Time Limit Exceeded (TLE) error.
Now as per the problem, we will try to optimize the solution to O(log n). Let's see how we can do this...
Optimal Approach
Intuition:
Let’s think about this problem differently. Imagine we are looking at any index in the array (except the first and last). The element at this index has two neighbours: one before it and one after it. These neighbours might be smaller or larger than the element at the current index (the index we are looking at).
Now, let’s focus on the element immediately after our current index. It can either be greater or smaller than the element at our current index. Let’s break this into two possibilities:
- Case 1: The next element is greater
- If the element to the right (the next element) is greater than the current element, it suggests that there might be a peak further along the right-hand side of the array.
- Case 2: The next element is smaller
- If the next element is smaller, it means that the current element is larger than the one to its right. This gives us hope that a peak might exist on the left-hand side, or perhaps the current element itself is the peak.
At each step, we choose the side that leads us toward the larger of the two elements (the current element and the one next to it). This ensures that we always move closer to a peak. The key idea here is that a peak is guaranteed to exist in the direction where the elements are increasing.
Why does this work?
If the next element is greater:
Moving toward increasing elements ensures that we’ll eventually find a peak. Why? Either we’ll find an element that is greater than its neighbour on the right (a peak), or we’ll reach the end of the array, where the last element will be the peak (since there’s no neighbour to compare it with). It’s like climbing a hill—if you find a slope going upward, you want to keep moving in that direction to reach the top.
If the next element is smaller:
Here, the slope is decreasing, which means the increasing part lies on the left-hand side of our current index. So we will move towards that side. This is because the current element is already larger than the next, and there’s a chance that the current element itself is the peak or a larger element exists further left. Imagine you’re climbing a hill again—if the slope starts going downward, you might have already reached the top.
Example
To make this clearer, let’s visualize what happens in a small example:
Suppose we have the array: [1, 3, 4, 7, 2]
- Suppose we start at index 2 (value = 4). The next element (index 3, value = 7) is greater. So, we move right.
- Now, at index 3 (value = 7). The next element (index 4, value = 5) is smaller. This means index 3 is a peak because 7 is greater than both its neighbours (4 and 5).
This shows how comparing the current element with its neighbour helps us decide which direction to explore.
By now, you might notice that this approach doesn’t require us to look at all the elements. Instead, we eliminate half of the array at every step based on whether we move left or right. This process of repeatedly dividing the search space in half is exactly how binary search works.
In binary search, we don’t need to search linearly; instead, we only explore the half of the array where a peak might exist.
To efficiently find the peak elements in an array using binary search, we will fix our current index as the middle index of the array.
- The left-hand side contains elements from the start of the array to the middle index.
- The right-hand side contains elements from the middle index to the end of the array.
Once we select the middle index of the array, we compare the element at this index with the next element. Based on this comparison, we decide which half of the array to search next.
If the next element is greater, it means the answer lies in the right half, and we eliminate the left half from our search. Conversely, if the next element is smaller, the answer is in the left half, so we eliminate the right half from our search.
By choosing the middle index and comparing it with its neighbour, we continuously reduce the search space by half. This is a very efficient way to find the peak element in an array using binary search. At every step, we eliminate half of the array from consideration.
For example:
- Start with the entire array: [1, 3, 4, 7, 5, 2]
- Middle index = 2 (value = 4), compared with the next element (value = 7).
- Since 7 is greater, focus on the right-hand side:
[7, 5, 2]
- Since 7 is greater, focus on the right-hand side:
- Middle index = 4 (value = 5), compared with the next element (value = 2).
- Since 2 is smaller, focus on the left-hand side:
[7, 5]
- Since 2 is smaller, focus on the left-hand side:
- Middle index = 3 (value = 7). Since 7 is greater than both its neighbours, it’s a peak.
Optimal Approach for Find Peak Element
Dry run
Input: nums = [1, 2, 3, 4, 5]
Output: 4
Explanation: 5 is the peak element and the index of element 5 is 4 so we return 4
Initial State:
- left = 0
- right = nums.size() - 1 = 4
Iteration 1:
- Calculate Midpoint:
- mid = (left + right) / 2 = (0 + 4) / 2 = 2
- nums[mid] = nums[2] = 3
- nums[mid + 1] = nums[3] = 4
- Comparison:
- Check if nums[mid] > nums[mid + 1] (i.e., 3 > 4).
- Condition is false, so move the left pointer to mid + 1.
- Update: left = 2 + 1 = 3
Iteration 2:
- Calculate Midpoint:
- mid = (left + right) / 2 = (3 + 4) / 2 = 3
- nums[mid] = nums[3] = 4
- nums[mid + 1] = nums[4] = 5
- Comparison:
- Check if nums[mid] > nums[mid + 1] (i.e., 4 > 5).
- Condition is false, so move the left pointer to mid + 1.
- Update: left = 3 + 1 = 4
Termination:
- Now, left = right = 4.
- The while loop terminates because left < right is false.
Return:
- The function returns left = 4.
Steps to write code
Step 1: Initialize Variables
- left initialized to 0. right initialized to the last index of the array (nums.size() - 1).
Step 2: Set Up a While Loop
- Use a loop that runs as long as left < right. The loop ensures the search space is reduced until we narrow it down to a single element.
Step 3: Calculate the Midpoint
- Inside the loop, calculate the midpoint mid = (left + right) / 2. This finds the middle index of the current search space.
Step 4: Compare nums[mid] with nums[mid + 1]
- If nums[mid] > nums[mid + 1]. This means the peak lies on the left side, so update right = mid.
- Otherwise, it means the peak lies on the right side, so update left = mid + 1.
Step 5: Return the Result
- When the loop terminates (left == right), the peak element is found at the index left.
- Return left.
Optimal Approach in All Languages
C++
class Solution {
public:
// Function to find the index of a peak element
int findPeakElement(vector<int>& nums) {
// Initialize left pointer to the start of the array
int left = 0;
// Initialize right pointer to the end of the array
int right = nums.size() - 1;
// Perform binary search
while (left < right) {
// Calculate the middle index
int mid = (left + right) / 2;
// If the middle element is greater than the next element
if (nums[mid] > nums[mid + 1]) {
// Narrow the search space to the left side
right = mid;
} else {
// Narrow the search space to the right side
left = mid + 1;
}
}
// Return the index of the peak element
return left;
}
};Java
public class Solution {
// Function to find the index of a peak element
public int findPeakElement(int[] nums) {
// Initialize left pointer to the start of the array
int left = 0;
// Initialize right pointer to the end of the array
int right = nums.length - 1;
// Perform binary search
while (left < right) {
// Calculate the middle index
int mid = (left + right) / 2;
// If the middle element is greater than the next element
if (nums[mid] > nums[mid + 1]) {
// Narrow the search space to the left side
right = mid;
} else {
// Narrow the search space to the right side
left = mid + 1;
}
}
// Return the index of the peak element
return left;
}
}Python
# Define the solution class
class Solution:
# Function to find the index of a peak element
def findPeakElement(self, nums: list[int]) -> int:
# Initialize left pointer to the start of the array
left = 0
# Initialize right pointer to the end of the array
right = len(nums) - 1
# Perform binary search
while left < right:
# Calculate the middle index
mid = (left + right) // 2
# If the middle element is greater than the next element
if nums[mid] > nums[mid + 1]:
# Narrow the search space to the left side
right = mid
else:
# Narrow the search space to the right side
left = mid + 1
# Return the index of the peak element
return leftJavascript
/**
* @param {number[]} nums
* @return {number}
*/
var findPeakElement = function(nums) {
// Initialize left pointer to the start of the array
let left = 0;
// Initialize right pointer to the end of the array
let right = nums.length - 1;
// Perform binary search
while (left < right) {
// Calculate the middle index
let mid = Math.floor((left + right) / 2);
// If the middle element is greater than the next element
if (nums[mid] > nums[mid + 1]) {
// Narrow the search space to the left side
right = mid;
} else {
// Narrow the search space to the right side
left = mid + 1;
}
}
// Return the index of the peak element
return left;
};Complexity Analysis of finding peak element in array Solution
Time Complexity: O(logn)
Step 1: Initializing Variables
- Variables left and right are initialized to the first and last indices of the array, respectively.
- These are simple assignments, each taking O(1) time.
- Overall: O(1).
Step 2: Binary Search
- The while (left < right) loop runs as long as the search space has more than one element.
- Inside the loop:
- Calculating Midpoint:
mid = (left + right) / 2 takes O(1) time. - Comparison:
The comparison nums[mid] > nums[mid + 1] also takes O(1) time. - Updating Pointers:
Based on the condition, either right = mid or left = mid + 1 is updated, which also takes O(1) time.
- Calculating Midpoint:
- Number of Iterations:
- In each iteration, the search space size is reduced by half. This is the key property of binary search.
- Initially, the search space is of size n (the length of the array). After each iteration, the size becomes:
n → n/2 → n/4 → n/8 → ... → 1 - The number of iterations required to reduce the search space to 1 is log₂(n), where n is the size of the array.
- Total Time in the Loop:
- Each iteration performs constant-time operations (O(1)), and there are log₂(n) iterations.
- Total time for the loop: O(log n).
Step 3: Returning the Result
- After exiting the loop, the peak index left is returned in O(1) time.
Overall Time Complexity
- The time complexity is dominated by the binary search loop, which takes O(log n).
- Other operations (initializations, comparisons, and returning the result) take constant time O(1).
Thus, the total time complexity is O(log n).
Space Complexity: O(1)
Auxiliary Space Complexity
Auxiliary space refers to the extra memory allocated by the algorithm during its execution (excluding input data storage).
Memory Usage:
- Variables:
- left, right, and mid are the only variables used during execution. Each of these is a simple integer, which takes O(1) space.
- No Recursion or Additional Data Structures:
- This algorithm does not use recursion, so there is no function call stack overhead.
- It also does not use any additional data structures (like arrays, stacks, or hash maps).
Auxiliary Space Complexity is: O(1).
Total Space Complexity
The input array nums is provided as an argument to the function. Its memory is not allocated by the algorithm, but it still contributes to the total space used.
Memory Usage:
- The input array nums of size n is stored in memory.
- This storage is external to the function and does not count toward the auxiliary space complexity but contributes to the total space complexity.
Input Space:
- The size of the input array is O(n), where n is the number of elements in the array.
Total Space Complexity is: O(n) (dominated by the input array).
Similar Problems
Now we have successfully tackled this problem, let's try these similar problems:-
You are given an integer mountain array arr of length n where the values increase to a peak element and then decrease.
Return the index of the peak element.
Your task is to solve it in O(log(n)) time complexity.
A peak element in a 2D grid is an element that is strictly greater than all of its adjacent neighbors to the left, right, top, and bottom.
Given a 0-indexed m x n matrix mat where no two adjacent cells are equal, find any peak element mat[i][j] and return the length 2 array [i,j].
You may assume that the entire matrix is surrounded by an outer perimeter with the value -1 in each cell.
You must write an algorithm that runs in O(m log(n)) or O(n log(m)) time.