# Higher Ground

> Somewhere the ground stops climbing.

Canonical URL: <https://datadriven.io/problems/higher_ground>

Domain: Python · Difficulty: medium · Seniority: L4

## 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.

## 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.

> **Trick to solving**
>
> At any index, if the element is smaller than its right neighbor, a peak must exist to the right (the boundary beyond the end is lower than anything). If it is not smaller than the right neighbor, this index is itself a peak candidate, so keep it and search left. Each comparison halves the window.

---

### 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**

```python
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.*

> **Time and space complexity**
>
> **Time:** O(log n). The window halves every iteration. **Space:** O(1): three integer variables, no recursion stack.

> **Interviewers watch for**
>
> Whether you can defend correctness. The argument: a peak always sits inside `[left, right]`. When `nums[mid] < nums[mid + 1]`, discarding the left half is safe because the rising slope must eventually crest or hit the boundary, both of which are inside the right half. State that out loud and you read as senior.

> **Common pitfall**
>
> Writing `right = mid - 1` in the else branch. When `nums[mid] >= nums[mid + 1]`, `mid` is still a live peak candidate, so excluding it can step right over the only peak and collapse onto a non-peak index.

---

## Common follow-up questions

- What if the buffer could contain plateaus of consecutive equal values? _(Tests that the strict 'greater than both neighbors' guarantee is what preserves O(log n).)_
- How would you return every peak index instead of just one? _(Tests that enumerating every peak forces an O(n) pass since no candidate can be skipped.)_
- What if this were a 2D grid and you needed a peak cell? _(Tests extending the gradient idea to two dimensions with a column-max reduction.)_
- Why does this work even though the buffer is never sorted? _(Tests the core insight that local gradient information, not global order, drives the halving.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/higher_ground)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.