Find Peak Element

Find Peak Element

What is this problem about?

The Find Peak Element interview question asks you to find any "peak" element in an array. A peak element is an element that is strictly greater than its neighbors. For elements at the boundaries, they only need to be greater than their single neighbor. You are guaranteed that nums[i] != nums[i+1] for all valid $i$. The goal is to find the index of any peak in $O(\log N)$ time.

Why is this asked in interviews?

This is a standard question at Apple, Amazon, and Google. It tests your ability to apply Binary Search to a non-sorted array. It evaluations if you understand the "climbing" property: if you are on a slope moving upwards, there must be a peak somewhere ahead of you (or at the end). It’s a core Binary Search interview pattern.

Algorithmic pattern used

This follows the Binary Search on a Monotonic Slope pattern.

1. Pointers: left = 0, right = n - 1.
2. Comparison: Look at nums[mid] and nums[mid + 1].
3. Movement:
   • If nums[mid] < nums[mid + 1], you are currently on an upward slope. A peak must exist to the right. Move left = mid + 1.
   • If nums[mid] > nums[mid + 1], you are on a downward slope or at a peak. A peak must exist to the left (including mid). Move right = mid.
4. Termination: When left == right, you've found a peak.

Example explanation

Array: [1, 2, 3, 1]

• left=0, right=3, mid=1 (2).
• $2 < 3$, so move left = 2.
• left=2, right=3, mid=2 (3).
• $3 > 1$, so move right = 2.
• left == right. Result index: 2 (value 3).

Common mistakes candidates make

• Linear Scan: Providing an $O(N)$ solution when the interviewer explicitly asks for $O(\log N)$.
• Boundary Handling: Errors in the comparison logic for the first or last elements (though the mid + 1 trick avoids this).
• Strictly Greater: Forgetting that if two adjacent elements are equal, the peak definition breaks (luckily the problem forbids this).

Interview preparation tip

Binary Search doesn't always require a sorted array. It only requires a way to discard half of the search space. In this Array interview pattern, the "slope" provides that discard logic.