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:
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.Solution in Python
To solve the problem of finding a peak element in an array in O(log n) time, we can use a binary search approach. Step-by-step explanation and the Python code implementation:
Explanation
- Binary Search Concept: Since we need to find a peak element and do it in logarithmic time, binary search is a suitable approach. We will use a modified binary search to find a peak element.
- Midpoint Comparison: For any element at the middle index, there are three possibilities:
- If the middle element is greater than its neighbors, it is a peak.
- If the middle element is less than the next element, there must be a peak in the right half.
- If the middle element is less than the previous element, there must be a peak in the left half.
- Recursive or Iterative Approach: We can implement this using an iterative approach to avoid potential stack overflow issues with deep recursion.
Python
from typing import List
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
# Initialize the left and right pointers for binary search
left, right = 0, len(nums) - 1
# Perform binary search
while left < right:
# Find the middle index
mid = (left + right) // 2
# If the mid element is greater than the next element, then the peak is in the left half (including mid)
if nums[mid] > nums[mid + 1]:
right = mid
else:
# Otherwise, the peak is in the right half (excluding mid)
left = mid + 1
# At the end of the loop, left and right will point to the peak element
return leftDetailed Comments:
- Initialization:
left, right = 0, len(nums) - 1: Initialize the left pointer to the start of the array and the right pointer to the end of the array.
- Binary Search Loop:
while left < right: Continue the loop until the left pointer is equal to the right pointer.mid = (left + right) // 2: Calculate the middle index of the current subarray.if nums[mid] > nums[mid + 1]: Check if the middle element is greater than the next element.right = mid: If true, move the right pointer to mid, searching the left half (including mid) in the next iteration.
else: left = mid + 1: If false, move the left pointer to mid + 1, searching the right half (excluding mid) in the next iteration.
- Return Peak Index:
return left: After the loop ends, left and right pointers converge to the same index, which is the peak element index.
Solution in Javascript
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var findPeakElement = function(nums) {
// Initialize the left and right pointers for binary search
let left = 0;
let right = nums.length - 1;
// Perform binary search
while (left < right) {
// Find the middle index
let mid = Math.floor((left + right) / 2);
// If the mid element is greater than the next element, then the peak is in the left half (including mid)
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
// Otherwise, the peak is in the right half (excluding mid)
left = mid + 1;
}
}
// At the end of the loop, left and right will point to the peak element
return left;
};Solution in Java
Java
class Solution {
public int findPeakElement(int[] nums) {
// Initialize the left and right pointers for binary search
int left = 0;
int right = nums.length - 1;
// Perform binary search
while (left < right) {
// Find the middle index
int mid = left + (right - left) / 2;
// If the mid element is greater than the next element, then the peak is in the left half (including mid)
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
// Otherwise, the peak is in the right half (excluding mid)
left = mid + 1;
}
}
// At the end of the loop, left and right will point to the peak element
return left;
}
}Solution in C#
C#
public class Solution {
public int FindPeakElement(int[] nums) {
// Initialize the left and right pointers for binary search
int left = 0;
int right = nums.Length - 1;
// Perform binary search
while (left < right) {
// Find the middle index
int mid = left + (right - left) / 2;
// If the mid element is greater than the next element, then the peak is in the left half (including mid)
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
// Otherwise, the peak is in the right half (excluding mid)
left = mid + 1;
}
}
// At the end of the loop, left and right will point to the peak element
return left;
}
}