Next greater element

easyMonotonic stackHash maps and sets target 15 min

Next greater element

Not solved yetLeetCode 496. Next Greater Element I

You get a list nums of distinct integers and a list queries. Every value in queries also appears in nums.

For each query value, find where it sits in nums and look to its right. Its answer is the first number you meet there that is bigger than it. If no bigger number appears to its right, its answer is -1.

Return a list with one answer per query, in the same order as queries.

Example 1

Inputqueries = [5, 2, 8], nums = [2, 5, 3, 8, 1]Output[8, 5, -1]

Right of the 5 come 3 and 8: the 3 is smaller, so the 8 is the first bigger one. Right of the 2, the 5 is bigger at once. Right of the 8 there is only a 1, so -1.

Example 2

Inputqueries = [4, 1], nums = [1, 3, 4]Output[-1, 3]

The 4 is last, so nothing is to its right. The answers follow the order of queries, not of nums.

Constraints

1 ≤ len(queries) ≤ len(nums) ≤ 10⁵
0 ≤ nums[i] ≤ 10⁵, and the values in nums are distinct.

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

Walk In what order will you visit the input?Notebook What will you write down as you go?Promise What stays true after every step?Cost Time and space, in Big O.

Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern