☕ DSA Java Articles

Topics › Binary Search › BS on 1D Arrays

Find peak element

Medium TUF ID 75 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array arr of n integers in which no two adjacent elements are equal. An element is a peak if it is strictly greater than both of its neighbours. The imaginary elements arr[-1] and arr[n] are treated as negative infinity, so the first element only needs to beat its right neighbour and the last element only needs to beat its left neighbour. Return the index of any peak. If the array has several peaks, any one of them is accepted.

Constraints: 1 ≤ n ≤ 10^5, values fit in a 32-bit signed integer, arr[i] != arr[i+1] for every valid i.

Example 1

arr = [1, 2, 3, 1]
answer = 2          // 3 is greater than both 2 and 1

Example 2

arr = [1, 2, 1, 3, 5, 6, 4]
answer = 1 or 5     // 2 is a peak (1 < 2 > 1) and so is 6 (5 < 6 > 4)

Approach 1: Brute force, linear scan

Intuition. The definition of a peak only involves an element and its two neighbours, so check every index directly. The out-of-range neighbours are negative infinity, which is the same as saying “the comparison on that side is automatically satisfied”.

Algorithm.

  1. For each index i from 0 to n - 1:
    • leftOk is true if i == 0 or arr[i-1] < arr[i].
    • rightOk is true if i == n - 1 or arr[i+1] < arr[i].
    • If both hold, return i.
  2. For valid input a peak always exists, so the loop always returns.
static int bruteForce(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        boolean leftOk = (i == 0) || arr[i - 1] < arr[i];
        boolean rightOk = (i == n - 1) || arr[i + 1] < arr[i];
        if (leftOk && rightOk) return i;
    }
    return -1;
}

Complexity. Time O(n): each element is checked once. Space O(1).

Why must a peak exist at all? Start at index 0. If it is not a peak, then arr[1] > arr[0]. Walk right as long as the values keep increasing; because the array is finite you must eventually either reach the last element (which is then a peak, since its right neighbour is minus infinity) or find an element whose right neighbour is smaller (which is a peak). This argument is exactly what the binary search exploits.

Approach 2: Optimal, binary search towards the larger neighbour

Intuition. Pick the middle element mid. If it is a peak, we are done. Otherwise at least one neighbour is larger. If arr[mid - 1] < arr[mid] we are on an ascending slope: the values are climbing to the right of mid, and by the argument above the climb must end in a peak somewhere in (mid, n-1]. If instead arr[mid - 1] > arr[mid], the values climb towards the left, so a peak must exist in [0, mid). Either way we can discard half the array without losing every peak.

To keep the comparisons arr[mid - 1] and arr[mid + 1] in range, handle n == 1 and the two ends first, then search [1, n - 2].

Algorithm.

  1. If n == 1, return 0. If arr[0] > arr[1], return 0. If arr[n-1] > arr[n-2], return n - 1.
  2. Set lo = 1, hi = n - 2.
  3. While lo <= hi:
    • mid = lo + (hi - lo) / 2.
    • If arr[mid] beats both neighbours, return mid.
    • If arr[mid] > arr[mid-1] (climbing), set lo = mid + 1.
    • Otherwise set hi = mid - 1.
static int optimal(int[] arr) {
    int n = arr.length;
    if (n == 1) return 0;
    if (arr[0] > arr[1]) return 0;
    if (arr[n - 1] > arr[n - 2]) return n - 1;
    int lo = 1, hi = n - 2;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) return mid;
        if (arr[mid] > arr[mid - 1]) lo = mid + 1;   // climbing: a peak must exist to the right
        else hi = mid - 1;                            // descending or in a valley: a peak must exist to the left
    }
    return -1;
}

Dry run on arr = [1, 2, 3, 1]:

lo hi mid arr[mid-1], arr[mid], arr[mid+1] decision
1 2 1 1, 2, 3 2 > 1 but 2 < 3: climbing, lo = 2
2 2 2 2, 3, 1 3 beats both: return 2

The else branch covers two situations: arr[mid] is on a descending slope (arr[mid-1] > arr[mid] > arr[mid+1]) or in a valley (arr[mid-1] > arr[mid] < arr[mid+1]). In both, the left neighbour is larger, so the climb towards the left guarantees a peak on that side. Picking the left side in the valley case is arbitrary; the right side would also contain a peak.

Complexity. Time O(log n): the search range halves every step. Space O(1).

Approach 3: Optimal, compact half-open form

Intuition. The special cases for the ends can be folded into the loop by comparing mid only with its right neighbour and keeping the invariant “a peak exists in [lo, hi]”. If arr[mid] < arr[mid + 1], the climb to the right guarantees a peak strictly after mid, so lo = mid + 1. Otherwise arr[mid] > arr[mid + 1] (equal is excluded by the constraint), so either mid is a peak or the climb to its left ends in one: hi = mid. Because mid < hi whenever lo < hi, mid + 1 is always a valid index, and the loop stops when lo == hi, which is the answer.

Algorithm.

  1. Set lo = 0, hi = n - 1.
  2. While lo < hi: compute mid; if arr[mid] < arr[mid+1], set lo = mid + 1, else set hi = mid.
  3. Return lo.
static int optimalCompact(int[] arr) {
    int lo = 0, hi = arr.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < arr[mid + 1]) lo = mid + 1;   // the peak is strictly to the right of mid
        else hi = mid;                                // arr[mid] > arr[mid + 1]: a peak is at mid or to its left
    }
    return lo;
}

Complexity. Time O(log n), Space O(1). Same bounds as Approach 2 with less code, but the correctness argument is slightly subtler, so learn the explicit version first.

Note that Approaches 2 and 3 can return different valid peaks on arrays with several peaks. For [1, 5, 1, 2, 1] the explicit search returns index 1 and the compact search returns index 3; both are correct. The Java tests therefore check “is the returned index a peak” rather than a fixed number whenever more than one peak exists.

Edge cases and pitfalls