# Peak Index in a Mountain Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/peak-index-in-a-mountain-array)
Canonical: https://scaleengineer.com/dsa/problems/peak-index-in-a-mountain-array
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [ByteDance](https://scaleengineer.com/companies/bytedance), [tcs](https://scaleengineer.com/companies/tcs), [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
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.

**Example 1:**

**Input:** arr = \[0,1,0\]

**Output:** 1

**Example 2:**

**Input:** arr = \[0,2,1,0\]

**Output:** 1

**Example 3:**

**Input:** arr = \[0,10,5,2\]

**Output:** 1

**Constraints:**

* `3 <= arr.length <= 105`
* `0 <= arr[i] <= 106`
* `arr` is **guaranteed** to be a mountain array.

# Approaches
## Linear Scan
This approach involves iterating through the array to find the peak element. A peak element is one that is greater than its immediate neighbors. Since the array is guaranteed to be a mountain array (strictly increasing then strictly decreasing), we can find the peak by identifying the first element that is greater than the next one.
**Time:** O(n), where n is the number of elements in the array. In the worst-case scenario (e.g., `[0, 1, 2, ..., n-2, n-3]`), we might have to traverse almost the entire array to find the peak. · **Space:** O(1), as we only use a few variables to store the index, requiring constant extra space.
**Pros:** Very simple to understand and implement.; Requires no complex logic.
**Cons:** Inefficient for large arrays as it has a linear time complexity.; Does not meet the `O(log n)` time complexity requirement specified in the problem description.
### Explanation
We can traverse the array from the beginning. The peak is the highest point, so the elements increase up to the peak and then decrease. This means the peak is the first element `arr[i]` for which `arr[i] > arr[i+1]`. We can iterate from the first element up to the second-to-last element and check this condition. The first time this condition is met, we have found our peak index and can return it immediately. Because the problem guarantees a mountain array of at least length 3, a peak is guaranteed to exist and will be found by this method.
```java
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i+1]) {
                return i;
            }
        }
        return -1; // Should not be reached given the problem constraints
    }
}
```
### Algorithm
*   Iterate through the array `arr` with an index `i` from `0` to `arr.length - 2`. *   In each iteration, check if `arr[i] > arr[i+1]`. *   If this condition is true, it means we have just passed the peak. The peak is at index `i`. Return `i`.

## Binary Search
A more efficient approach that meets the `O(log n)` time complexity requirement is to use binary search. The properties of the mountain array allow us to discard half of the search space in each step. We can determine whether the middle element is on the ascending or descending slope and adjust our search range accordingly.
**Time:** O(log n), where n is the length of the array. This is because binary search halves the search space in each iteration. · **Space:** O(1), as it only requires a few variables for the pointers and the middle index, using constant extra space.
**Pros:** Highly efficient and optimal for this problem.; Meets the `O(log n)` time complexity requirement.
**Cons:** Slightly more complex to reason about and implement correctly compared to a linear scan.; Requires careful handling of pointers and boundary conditions to avoid infinite loops or incorrect results.
### Explanation
The core idea is to apply binary search on the array indices. We maintain two pointers, `low` and `high`, which define the current search space.
In each step, we calculate the middle index `mid`. We then compare `arr[mid]` with its right neighbor `arr[mid + 1]`.
- If `arr[mid] < arr[mid + 1]`, it means `mid` is on the ascending slope of the mountain. The peak must be located to the right of `mid`. Therefore, we can safely discard the left half of the search space, including `mid`, by setting `low = mid + 1`.
- If `arr[mid] > arr[mid + 1]`, it means `mid` is either the peak itself or on the descending slope. In this case, the peak is at `mid` or to its left. We can discard the right half, but we must keep `mid` in our search space as it could be the peak. We do this by setting `high = mid`.
We repeat this process until `low` and `high` converge (`low == high`). The index they converge to is the peak index.
```java
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int low = 0;
        int high = arr.length - 1;
        
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] < arr[mid + 1]) {
                // We are in the increasing part of the array
                // The peak is to the right
                low = mid + 1;
            } else {
                // We are in the decreasing part of the array, or at the peak
                // The peak is at mid or to the left
                high = mid;
            }
        }
        // low and high will converge to the peak index
        return low;
    }
}
```
### Algorithm
*   Initialize two pointers, `low = 0` and `high = arr.length - 1`. *   Loop as long as `low < high`. *   Calculate the middle index: `mid = low + (high - low) / 2`. *   Check if `arr[mid]` is less than `arr[mid + 1]`. *   If true, `mid` is on the ascending slope. The peak is in the range `[mid + 1, high]`. Update `low = mid + 1`. *   If false, `mid` is on the descending slope or is the peak. The peak is in the range `[low, mid]`. Update `high = mid`. *   When the loop terminates, `low` and `high` will be equal and point to the peak index. Return `low`.

# Solutions
### Java

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

```

### JavaScript

```javascript
/** * @param {number[]} arr * @return {number} */ var peakIndexInMountainArray =
  function (arr) {
    let left = 1;
    let right = arr.length - 2;
    while (left < right) {
      const mid = (left + right) >> 1;
      if (arr[mid] > arr[mid + 1]) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  };

```

### CPP

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

```

### Python

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

```