Find Peak Element

Problem Link

find-peak-element

Problem Statement

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find any peak element and return its index.

You may assume:

• nums[-1] = nums[n] = -∞ (i.e., elements outside the array are always smaller)

• There is at least one peak in the array

• If there are multiple peaks, returning the index of any one of them is acceptable

The algorithm must run in O(log n) time complexity.

Examples

• Input: nums = [1, 2, 3, 1]
  Output: 2
  Explanation: 3 is a peak element, located at index 2.

• Input: nums = [1, 2, 1, 3, 5, 6, 4]
  Output: 5
  Explanation: 6 is a peak, located at index 5. Index 1 (value 2) is also valid.

Constraints

• 1 <= nums.length <= 1000

• -2^31 <= nums[i] <= 2^31 - 1

• nums[i] != nums[i + 1] for all valid i

Intuition

We are required to find a peak in logarithmic time, which strongly suggests using binary search.

We can think of the array as a mountain range:

• If the mid element is greater than its right neighbor, the peak must lie on the left side (including mid).

• If the mid element is less than its right neighbor, the peak must lie on the right side (excluding mid).

This idea is valid because eventually, we will reach a point where an element is greater than both neighbors.

Approach

1. Initialize start = 0, end = nums.length - 1

2. Use binary search:

   • While start < end:

     • Calculate mid = start + (end - start) / 2

     • If nums[mid] > nums[mid + 1], then search in the left half including mid: end = mid

     • Else, search in the right half: start = mid + 1

3. When the loop ends, start == end, which points to a peak.

4. Return start

Code in Java

class Solution {
    public int findPeakElement(int[] nums) {
        int start = 0;
        int end = nums.length - 1;

        while (start < end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] > nums[mid + 1]) {
                end = mid; // peak is on the left or at mid
            } else {
                start = mid + 1; // peak is on the right
            }
        }

        return start; // or return end (both are equal here)
    }
}

Time and Space Complexity

• Time Complexity: O(log n)
  We halve the search space in each iteration.

• Space Complexity: O(1)
  No extra memory is used beyond a few variables.

Dry Run

Input:

nums = [1, 2, 1, 3, 5, 6, 4]

Steps:

1. start = 0, end = 6 → mid = 3, nums[3] = 3, nums[4] = 5
   → 3 < 5 → move right → start = 4

2. start = 4, end = 6 → mid = 5, nums[5] = 6, nums[6] = 4
   → 6 > 4 → move left → end = 5

3. start = 4, end = 5 → mid = 4, nums[4] = 5, nums[5] = 6
   → 5 < 6 → move right → start = 5

Now start == end == 5

Return 5

Conclusion

This problem is a great example of binary search used creatively to satisfy custom conditions. By analyzing the slope of the array (increasing or decreasing at the midpoint), we efficiently narrow down the search space to locate a peak. The logic guarantees that we will always find at least one peak using this method in O(log n) time.