Next Greater Element

Try to solve the Next Greater Element problem.

We'll cover the following

Statement#

Given the two distinct integer arrays, nums1 and nums2, where nums1 is a subset of nums2, find all the next greater elements for nums1 values in the corresponding places of nums2.

In general, the next greater element of an element, xx, in an array is the first greater element present on the right side of xx in the same array. However, in the context of this problem, for each element xx in nums1, find the next greater element present on the right side of xx in nums2 and store it in the ans array. If there is no such element, store −1-1 for this number. The ans array should be of the same length as nums1, and the order of the elements in the ans array should correspond to the order of the elements in nums1.

Return the ans array after finding the next greater elements.

Note: The input data may or may not be sorted.

Constraints:

  • 1≤1 \leq nums1.length ≤\leq nums2.length ≤103\leq 10^3
  • 0≤0 \leq nums1[i], nums2[i] ≤104\leq 10^4
  • nums1 have distinct integers.
  • nums2 have distinct integers.
  • All integers in nums1 also appear in nums2.

Examples#

Created with Fabric.js 3.6.6 Input Output nums1 1 2 3 nums2 1 2 3 4 5 ans 2 3 4 Sample example 1 In nums2, the number greater than 1 is 2, so we place 2 at its index in the ans array. Similarly, the number greater than 2 is 3, so we place 3 at its index in the ans array. Lastly, the number greater than 3 is 4, so we place 4 at its index in the ans array.

1 of 2

Created with Fabric.js 3.6.6 Input Output Sample example 2 nums1 5 3 4 nums2 2 4 5 3 ans -1 -1 5 In nums2, there is no number greater than 5, so we place -1 at itsindex in the ans array. Similarly, there is no number greater than 3, sowe place -1 at its index in the ans array. Lastly, the number greater than 4 is 5, so we place 5 at its index in the ans array.

2 of 2

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Next Greater Element

1

What is the output if the following arrays are given as input?

nums1 = [5, 4, 7]

nums2 = [4, 5, 7, 3]

A)

ans = [7, 7, 3]

B)

ans = [7, 7, -1]

C)

ans = [7, 5, -1]

D)

ans = [7, 5, 3]

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Create an empty stack and an empty hash map.

Iterate over nums2, and for each element, compare it with the top element of the stack.

If the current element of nums2 is greater than the top element, pop the top element and put a key-value pair in the hash map with the popped element as the key and the current element of nums2 as the value.

Push the current element onto the stack.

Repeat the process above until we have iterated over all elements in nums2.

Finally, iterate over nums1, and for each element, append its corresponding value from the hash map to a new array ans and return the ans array as the final result.

Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > main.py
Input #1
Input #2
%0 node_01 2 node_11 4
Visualization for Input #1
Next Greater Element

Solution: Logger Rate Limiter

Solution: Next Greater Element