The Horizon Scanner

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
Sigmoid

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.

For each position, what is coming up ahead?

Example

Input:

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

Output:

[4,2,4,-1,-1]

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

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

Common follow-up questions