Higher Ground

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Spirit Airlines

Problem

You're scanning a buffer of unsorted sensor readings for a peak: any index in nums whose value is strictly greater than both of its neighbors, where the space just past either end of the buffer counts as lower than any reading. Return the index of any one such peak. The buffer can be large and lookups must stay logarithmic, so walking every reading is off the table.

Somewhere the ground stops climbing.

Example 1

Input:

nums = [1,2,3,1]

Output:

2

Example 2

Input:

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

Output:

5

Worked solution and explanation

What this really is

Strip the mountain imagery and this is binary search with no sorted array to lean on. Most candidates freeze right here: 'binary search needs sorted data, so I'll just scan for the max in O(n).' That reflex misses the one fact that cracks the problem. Any index whose value rises toward its right neighbor guarantees a peak somewhere to the right, because the buffer cannot climb forever past a boundary that counts as negative infinity. That single gradient check, not any global order, is what lets you throw away half the buffer every step.

Break down the requirements

Step 1: Set up the search boundaries

left starts at 0, right at len(nums) - 1. The invariant you are protecting: a peak always lives somewhere in the closed range [left, right].

Step 2: Compare the midpoint with its right neighbor

Compute mid. If nums[mid] < nums[mid + 1], the slope is rising, so a peak lies strictly to the right: move left to mid + 1. Otherwise mid could be the peak itself, so move right to mid and keep it in range.

Step 3: Terminate when the window collapses

When left == right the window has collapsed to one index, and the invariant guarantees that index is a peak. Return it.

The solution

Binary search on the local gradient
def find_peak_element(nums: list) -> int:
    left = 0
    right = len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < nums[mid + 1]:
            left = mid + 1
        else:
            right = mid
    return left

No sorted assumption anywhere: the comparison reads the slope, not the order.

Common follow-up questions