# The Horizon Scanner

> For each position, what is coming up ahead?

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

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a list of integers, return a list of the same length where position i is the first element to the right strictly greater than nums[i], or -1 if no such element exists.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the **next greater element** problem, which uses a **monotonic stack**. It probes whether a candidate can recognize the stack-based pattern that transforms a naive O(n^2) approach into O(n).

> **Trick to Solving**
>
> Use a stack that stores indices of elements awaiting their next greater element. When you encounter a value larger than the stack top, pop and record. The stack maintains a decreasing sequence of unresolved elements.

---

### Break down the requirements

#### Step 1: Initialize a result array with -1

Default to -1 for elements with no greater element to their right.

#### Step 2: Use a stack of indices

Push each index onto the stack. Before pushing, pop all indices whose values are smaller than the current element.

#### Step 3: Set the result for each popped index

The current element is the next greater element for every popped index.

---

### The solution

**Monotonic stack for next greater element**

```python
def next_greater(nums: list) -> list:
    n = len(nums)
    result = [-1] * n
    stack = []
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(n). Each index is pushed and popped at most once.
> 
> **Space:** O(n) for the stack and result array.

> **Interviewers Watch For**
>
> Whether you recognize the monotonic stack pattern. Brute-force O(n^2) is easy to write but shows a gap in algorithmic knowledge.

> **Common Pitfall**
>
> Using strict `<` vs `<=` in the comparison. The problem asks for strictly greater, so equal values should not trigger a pop.

---

## Common follow-up questions

- How would you find the next greater element in a circular array? _(Tests iterating `2*n` indices with modular arithmetic.)_
- What about the previous greater element? _(Tests iterating right to left with the same stack technique.)_
- What is a monotonic stack and when do you use it? _(Tests general pattern recognition for temperature, stock span, and histogram problems.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_horizon_scanner)
- [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). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.