Solution to LeetCode Next Greater Element Ⅰ in Python This is my solution to LeetCode's &quot;Next Greater Element Ⅰ&quot;:

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1's elements in the corresponding places of nums2.
The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

class Solution:
    
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -&gt; List[int]:
        need, ready, next_greater = set(nums1), set(), {}
        for n in nums2:
            for k in ready:
                if k &lt; n:
                    next_greater[k] = n
            ready = {k for k in ready if k not in next_greater}
            if n in need and n not in next_greater and n not in ready:
                ready.add(n)
        return [next_greater[k] if k in next_greater else -1 for k in nums1]

The nextGreaterElement method accepts 2 lists. Neither list contains duplicates, and nums1 is a subset of nums2. For every num in nums1, it will output the first number greater than num positioned to the right of num in nums2, or -1 is none is found. e.g.:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]

I loop through the keys in ready, and the body of the loop does nothing unless k &lt; n. len(ready) can be very large relative to the number of values that satisfy k &lt; n. This seems like a very common thing so I'm wondering if there's a more explicit/pythonic way to write this?
Or should I be using a different data structure entirely?
Since list one is a subset of list two, iterating over two lists can be avoided. This can be achieved by finding the next greater element of each element for the bigger list and storing the result in a hash table.

To calculate the next greater element of each element in a list we can iterate the list. For each element, we can find the next greater element by again iterating the list. This approach is simple but will have O(n^2) complexity.

Another approach is by using stack. 


First, push the first element of the list int the stack. 
Now iterate the list and compare the top element of the stack with the current element of the list. 
If the current element is greater than the top element then that means the current element is the next greater element of the top element of the stack. Store this result in a dictionary. Pop the top element out of the stack. 
Repeat above two steps until the stack top element is greater than the current element or stack is empty. 
At the end of each iteration push the current element in the stack.


The code will make things clearer: 


def calculate_nge_dict(arr):

    nge_dict = {}
    stack_ = []
    stack_.append(arr[0])
    nge_dict[arr[0]] = -1
    for i in arr[1:]:
        next_ = i
        nge_dict[next_] = -1
        while stack_:
            top_ = stack_.pop()
            if next_ &lt;= top_:
                stack_.append(top_)
                break
            else:
                nge_dict[top_] = next_
        stack_.append(next_)
    return nge_dict

def next_greater_element(nums1, nums2):
    nge_dict = calculate_nge_dict(nums2)
    return [nge_dict[i] for i in nums1]



You can get a better understanding of the algorithm from this answer.