Solution to LeetCode Next Greater Element I in Python

Question

This is my solution to LeetCode's "Next Greater Element I":

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]) -> List[int]:
 need, ready, next_greater = set(nums1), set(), {}
 for n in nums2:
 for k in ready:
 if k < 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 < n. len(ready) can be very large relative to the number of values that satisfy k < 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?

• NightDriveDrones: @dfhwze My question is more about writing Python loops in general, not my specific implementation of the loop. Would StackOverflow be a better place for that kind of question?
• dfhwze: No this is the correct place for it. You added a description of the problem statement, so it's on-topic now.

Answer 1

Your code seems unnecessarily complicated.

nums1 is subset of nums2. So no need to iterate over nums2. Because nums2 may be bigger than nums1

Here's the algo;

1. Take a number n from nums1
2. Find n's index in nums2. Because nums1 is subset of nums2 n will definitely be found.
3. Check if there's a number say m which is greater than n starting from the index + 1 index at nums2
4. If found output the number

5. Otherwise output -1

   class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
    output = []
    for n in nums1:
    idx = nums2.index(n)
    for m in nums2[idx+1:]:
    if m > n:
    output.append(m)
    break
    else:
    output.append(-1)
    return output
   

   Finding index sucks time. To optimize the index can be pre-calculated.

   output = []
   index = { n: i for i, n in enumerate(nums2) }
   for n in nums1:
    idx = index[n]
    for m in nums2[idx+1:]:
    if m > n:
    output.append(m)
    break
    else:
    output.append(-1)
   return output
   

• NightDriveDrones: Implementation details of Python's list.index might make this faster (I don't know), but the algorithm you're proposing is slower asymptotically as all elements of nums2 will be iterated for every element in nums1 (O(nm)) vs iterating each list once
• Nizam Mohamed: @user107870 that's good point
• Nizam Mohamed: @user107870 reduced iteration

Answer 2

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_ <= 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.