Skip to main content

75. Find Peak Element

mediumAsked at Datadog

Find any peak element in O(log n). Datadog asks this for the non-monotonic binary-search pattern — peak detection in metric streams uses the same uphill-direction logic.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — direct analog to streaming peak detection.

Problem

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

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

Example 2

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

Approaches

1. Linear scan

Walk and find any element greater than both neighbors.

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

Tradeoff: O(n) — violates the constraint.

2. Binary search uphill (optimal)

If nums[mid] < nums[mid+1], a peak exists to the right. Else, it exists at mid or left.

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;
    else hi = mid;
  }
  return lo;
}

Tradeoff: O(log n) — walking uphill guarantees we converge to a peak.

Datadog-specific tips

Datadog grades on the 'walk uphill' insight. Since boundaries are -infinity, going uphill always lands on a peak. Articulate why the binary search converges before coding.

Common mistakes

  • Using <= instead of < — when nums[mid] == nums[mid+1], you can't tell which side has the peak (but the problem disallows equality).
  • Using hi = mid - 1 instead of hi = mid — could overshoot the peak.
  • Trying to find THE peak instead of ANY peak.

Follow-up questions

An interviewer at Datadog may pivot to one of these next:

  • Find Peak Element II (2D) — same idea per row.
  • Peak Index in Mountain Array (LC 852).
  • Datadog-style: locate a peak in a streaming metric without scanning the whole history.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does walking uphill find a peak?

If you always step toward the higher neighbor, and the boundary is -infinity, you must eventually reach a point where both neighbors are lower — a peak.

Multiple peaks?

Any one is acceptable. The binary search finds whichever lies in the uphill direction it chose.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →