# Find Peak Element
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-peak-element)
Canonical: https://scaleengineer.com/dsa/problems/find-peak-element
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Tekion](https://scaleengineer.com/companies/tekion), [TikTok](https://scaleengineer.com/companies/tiktok), [Visa](https://scaleengineer.com/companies/visa), [Wix](https://scaleengineer.com/companies/wix), [eBay](https://scaleengineer.com/companies/ebay), [Commvault](https://scaleengineer.com/companies/commvault), [Snap](https://scaleengineer.com/companies/snap), [Zepto](https://scaleengineer.com/companies/zepto), [Databricks](https://scaleengineer.com/companies/databricks), [IXL](https://scaleengineer.com/companies/ixl), [Waymo](https://scaleengineer.com/companies/waymo)
---
## Problem
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.

**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`.

# Approaches
## Linear Scan
This approach involves a simple linear scan through the array. We iterate over each element and check if it satisfies the condition of being a peak: being strictly greater than its adjacent neighbors. Special care is taken for the first and last elements of the array, as they only have one neighbor to compare against.
**Time:** O(n) · **Space:** O(1)
**Pros:** The logic is straightforward and easy to understand.; It's simple to implement.
**Cons:** The time complexity of O(n) does not meet the problem's requirement of an O(log n) solution.; It is inefficient for large input arrays as it may need to scan the entire array in the worst-case scenario (e.g., a sorted array where the peak is the last element).
### Explanation
The brute-force method is to iterate through the `nums` array and check each element to see if it's a peak. The problem statement implies that `nums[-1]` and `nums[n]` are negative infinity, which simplifies the logic for the boundary elements.

1.  **Single Element Array**: If the array contains only one element, that element is a peak by definition. We return index 0.
2.  **First Element**: We check if `nums[0]` is greater than `nums[1]`. If it is, `nums[0]` is a peak.
3.  **Last Element**: We check if `nums[n-1]` is greater than `nums[n-2]`. If it is, `nums[n-1]` is a peak.
4.  **Middle Elements**: We loop from the second element to the second-to-last element. For each element `nums[i]`, we check if it's greater than both `nums[i-1]` and `nums[i+1]`. 

Since the problem guarantees that a peak always exists, this scan will find and return the index of one of the peaks.

```java
class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return 0;
        }
        // Check if the first element is a peak
        if (nums[0] > nums[1]) {
            return 0;
        }
        // Check if the last element is a peak
        if (nums[n - 1] > nums[n - 2]) {
            return n - 1;
        }
        // Check the elements in the middle
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                return i;
            }
        }
        return -1; // This line is unreachable given the problem constraints
    }
}
```
### Algorithm
*   Handle the edge case where the array has only one element by returning index 0.
*   Check if the first element `nums[0]` is a peak. This is true if `nums[0] > nums[1]`. If so, return 0.
*   Check if the last element `nums[n-1]` is a peak. This is true if `nums[n-1] > nums[n-2]`. If so, return `n-1`.
*   Iterate through the rest of the array from index `i = 1` to `n-2`.
*   For each element `nums[i]`, check if it is strictly greater than both its left neighbor `nums[i-1]` and its right neighbor `nums[i+1]`.
*   If the condition `nums[i] > nums[i-1] && nums[i] > nums[i+1]` is met, `nums[i]` is a peak. Return its index `i`.
*   Since the problem guarantees a peak exists, the function will always return an index from one of these checks.

## Binary Search
The `O(log n)` time complexity requirement strongly suggests a binary search-based approach. Although the array is not sorted, we can use the properties of a peak to our advantage. By comparing the middle element with its neighbor, we can determine whether a peak is guaranteed to exist in the left or right half of the current search space, allowing us to eliminate half of the elements in each step.
**Time:** O(log n) · **Space:** O(1)
**Pros:** Highly efficient, with a time complexity of O(log n), which meets the problem's constraints.; The space complexity is constant, O(1).; It is the optimal solution for this problem.
**Cons:** The underlying logic is more complex and less intuitive than a simple linear scan.; Requires careful handling of pointers and loop conditions to ensure correctness.
### Explanation
This optimal approach uses a modified binary search algorithm. The key idea is that for any given element `nums[mid]`, we can decide which side of it must contain a peak.

We maintain a search space defined by `left` and `right` pointers. In each iteration, we examine `nums[mid]` and its right neighbor `nums[mid + 1]`:

*   **Case 1: `nums[mid] < nums[mid + 1]`**
    This indicates that we are on an upward slope. Since we know the array must eventually go down (as `nums[n] = -∞`), there must be a peak somewhere to the right of `mid`. Therefore, we can safely discard the left part of the array, including `mid`, and continue our search in the range `[mid + 1, right]`.

*   **Case 2: `nums[mid] > nums[mid + 1]`**
    This indicates that we are on a downward slope. `nums[mid]` itself might be a peak, or there might be an even higher peak to its left (since `nums[-1] = -∞`). In either scenario, a peak is guaranteed to exist in the range `[left, mid]`. We can discard the right part and continue our search in this new range.

The loop continues until the search space is narrowed down to a single element (`left == right`). This single element is guaranteed to be a peak.

```java
class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) {
                // Peak is in the right half
                left = mid + 1;
            } else {
                // Peak is in the left half, including mid
                right = mid;
            }
        }
        // At the end of the loop, left == right, which is the index of a peak
        return left;
    }
}
```
### Algorithm
*   Initialize two pointers, `left = 0` and `right = nums.length - 1`.
*   Enter a loop that continues as long as `left < right`.
*   Calculate the middle index `mid = left + (right - left) / 2`.
*   Compare the element at the middle index, `nums[mid]`, with its right neighbor, `nums[mid + 1]`.
*   If `nums[mid] < nums[mid + 1]`, it means we are on an 'uphill' slope. A peak must exist to the right of `mid`. So, we can discard the left half of the search space by setting `left = mid + 1`.
*   If `nums[mid] >= nums[mid + 1]`, it means we are on a 'downhill' slope. The element `nums[mid]` could be a peak, or a peak exists to its left. So, we are certain a peak lies in the left half (including `mid`). We discard the right half by setting `right = mid`.
*   The loop terminates when `left` and `right` pointers converge (`left == right`). This final index is guaranteed to be a peak.

# Solutions
### Java

```java
class Solution { public int findPeakElement ( int [] nums ) { int left = 0 , right = nums . length - 1 ; while ( left < right ) { int mid = ( left + right ) >> 1 ; if ( nums [ mid ] > nums [ mid + 1 ]) { right = mid ; } else { left = mid + 1 ; } } return left ; } }
```

### CPP

```cpp
class Solution { public: int findPeakElement ( vector < int >& nums ) { int left = 0 , right = nums . size () - 1 ; while ( left < right ) { int mid = left + right >> 1 ; if ( nums [ mid ] > nums [ mid + 1 ]) { right = mid ; } else { left = mid + 1 ; } } return left ; } };
```

### Python

```python
class Solution : def findPeakElement ( self , nums : List [ int ]) -> int : left , right = 0 , len ( nums ) - 1 while left < right : mid = ( left + right ) >> 1 if nums [ mid ] > nums [ mid + 1 ]: right = mid else : left = mid + 1 return left
```