# Python Solution with O(n)

• ``````        d = {}
st = []
ans = []

for x in nums:
while len(st) and st[-1] < x:
d[st.pop()] = x
st.append(x)

for x in findNums:
ans.append(d.get(x, -1))

return ans
``````

• ``````        d = {}
st = []
ans = []

for x in nums:
while len(st) and st[-1] < x:
d[st.pop()] = x
st.append(x)

for x in findNums:
ans.append(d.get(x, -1))

return ans
``````

• How do you define O(n)? If you consider the complexity of building the hashmap, it will be O(N^2)

• @sylvanyang it use the stack, in normal average, it is O(1) for st, so it is O(n)

• @harshkothari410 Hello! Can you help me for explanation of the whole idea of algorithm? thank you

• @lusaty First, He builds a map which stores the {item: the next big item in nums2}. In pycharm, you can set some break points and debug it to see what happened.

• You can write this solution much shorter using just 6 lines.

``````def nextGreaterElement(self, findNums, nums):
st, d = [], {}

for v in nums:
while len(st) and st[-1] < v:
d[st.pop()] = v
st.append(v)

return map(lambda x: d.get(x, -1), findNums)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.