Skip to main content

27. Find Peak Element

mediumAsked at Tripadvisor

Locate a local maximum in an unsorted array in O(log n) — Tripadvisor uses binary search on unimodal signals to find peak engagement periods in destination popularity curves and seasonal booking trend data.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

A peak element is one that is strictly greater than its neighbors. Given a 0-indexed integer array nums, find a peak element and return its index. The array may contain multiple peaks; return the index of any peak. You must write an algorithm that runs in O(log n) time. Assume nums[-1] = nums[n] = -∞.

Constraints

  • 1 <= nums.length <= 1000
  • -2^31 <= nums[i] <= 2^31 - 1
  • nums[i] != nums[i + 1] for all valid i

Examples

Example 1

Input
nums = [1,2,3,1]
Output
2

Explanation: Index 2 (value 3) is a peak: 3 > 2 and 3 > 1.

Example 2

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

Explanation: Either index 1 or 5 is valid; returning 5 (value 6).

Approaches

1. Linear scan

Scan left to right; return the first index where nums[i] > nums[i+1]. O(n) — fails the O(log n) requirement but useful to state first.

Time
O(n)
Space
O(1)
function findPeakElement(nums) {
  for (let i = 0; i < nums.length - 1; i++) {
    if (nums[i] > nums[i + 1]) return i;
  }
  return nums.length - 1;
}

Tradeoff:

2. Binary search on slope direction (optimal)

Binary search: if nums[mid] < nums[mid+1], a peak exists to the right (ascending slope); otherwise it exists at mid or to the left. Converges to a peak in O(log n).

Time
O(log n)
Space
O(1)
function findPeakElement(nums) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] < nums[mid + 1]) {
      lo = mid + 1; // ascending: peak is to the right
    } else {
      hi = mid;     // descending: peak is at mid or left
    }
  }
  return lo;
}

Tradeoff:

Tripadvisor-specific tips

Tripadvisor's data team frequently needs to find local maxima in engagement metrics — peak review seasons, highest-traffic destination days — and the O(log n) binary search is the expected answer here. The tricky part is justifying correctness: explain that because nums[-1] and nums[n] are -infinity, every strictly monotone segment must end at a peak, so binary search can always halve the search space by following the upward slope. Draw the invariant before coding — interviewers check whether you can reason about binary search correctness, not just copy the template.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Find Peak Element and other Tripadvisor interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →