Skip to main content

21. Find Peak Element

mediumAsked at Databricks

Locate any local maximum in O(log n) — Databricks ties this to binary-search strategies for finding optimal partition-split points in Delta Lake's data-skipping index.

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

Problem

A peak element is strictly greater than its neighbors. Given an integer array nums where nums[i] != nums[i+1], find a peak element and return its index. If multiple peaks exist, return any. You must write an O(log n) algorithm.

Constraints

  • 1 <= nums.length <= 1000
  • -2^31 <= nums[i] <= 2^31 - 1
  • nums[i] != nums[i+1] for all valid i
  • nums[-1] = nums[n] = -infinity (imaginary sentinels)

Examples

Example 1

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

Explanation: 3 is a peak: 3 > 2 and 3 > 1.

Example 2

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

Explanation: 6 is a peak; index 1 (2) also qualifies.

Approaches

1. Linear scan

Walk the array and return the first index where nums[i] > nums[i+1]. Violates the O(log n) requirement.

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

At mid, if nums[mid] < nums[mid+1] the peak must lie to the right (slope is rising); otherwise it lies at mid or to the left. Narrows the search space by half each iteration.

Time
O(log n)
Space
O(1)
function findPeakElement(nums) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] < nums[mid + 1]) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  return lo;
}

Tradeoff:

Databricks-specific tips

The interviewer is checking whether you can apply binary search to a non-sorted array by reasoning about slope rather than value. Verbalize the invariant: 'the peak is guaranteed to exist in [lo, hi] because the array must turn around somewhere within the bounds.' Databricks engineers value invariant-driven reasoning — it maps to how they think about data-skipping guarantees in file statistics.

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 Databricks interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →