Find a Peak Element

Interview Problem Interview Medium Array Binary Search

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.findPeakElement(nums). Adjacent values differ and values outside the array are negative infinity. Return any peak index in O(log n).

Starter code

class Solution:
    def findPeakElement(self, nums):
        pass

Test cases

interior-peak

{
  "args": [
    [
      1,
      2,
      3,
      1
    ]
  ]
}

Expected: 2

Wizard outline

Step 1: Initialize Solution.findPeakElement
Replace the empty starter with the first real state owned by Solution.findPeakElement. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Pass the Two Value Slope case
Complete the readable core algorithm for one representative Interview case. Use the local slope between middle and middle+1 to retain a side guaranteed to contain a peak.
Step 3: Harden the Interior Peak boundary
Repair the reviewed boundary and pass the complete submission contract. Following an ascending edge right must eventually reach a peak before negative infinity; following a descending edge left has the symmetric guarantee. Each step retains a peak-containing interval until one index remains.

Footguns and prerequisites

The function returns an index, not the peak value.
arrays strings two pointers sliding window

Reviewed references

LeetCode 162 — Find Peak Element

Practice prerequisites

Find the First True Boundary(opens in a new tab)
Find the First True Boundary isolates every index before left is known false, while every index at or after right is known true or the sentinel len(flags). That focused state discipline is required when implementing find peak element as a complete Interview Problem.

Recommended approach and implementation

Binary search the slope: move right to middle on a descending edge, otherwise move left to middle+1.

Why it works: Following an ascending edge right must eventually reach a peak before negative infinity; following a descending edge left has the symmetric guarantee. Each step retains a peak-containing interval until one index remains.

class Solution:
    def findPeakElement(self, nums):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        left, right = 0, len(nums) - 1
        while left < right:
            middle = (left + right) // 2
            if nums[middle] > nums[middle + 1]:
                right = middle
            else:
                left = middle + 1
        return left