# Python solution with detailed explanation

• Solution

Next Greater Element I https://leetcode.com/problems/next-greater-element-i/

Algorithm

• https://discuss.leetcode.com/topic/77916/java-10-lines-linear-time-complexity-o-n-with-explanation
• Suppose we have a decreasing sequence followed by a greater number. For example [5, 4, 3, 2, 1, 6] then the greater number 6 is the next greater element for all previous numbers in the sequence.
• We use a stack to keep a decreasing sub-sequence, whenever we see a number x greater than stack.peek() we pop all elements less than x and for all the popped ones, their next greater element is x.
• For example [9, 8, 7, 3, 2, 1, 6]. The stack will first contain [9, 8, 7, 3, 2, 1] and then we see 6 which is greater than 1 so we pop 1 2 3 whose next greater element should be 6.
``````class Solution(object):
def nextGreaterElement(self, findNums, nums):
"""
:type findNums: List[int]
:type nums: List[int]
:rtype: List[int]
"""
cache, st = {}, []
for x in nums:
if len(st) == 0:
st.append(x)
elif x <= st[-1]:
st.append(x)
else:
while st and st[-1] < x:
cache[st.pop()] = x
st.append(x)
result = []
for x in findNums:
if x in cache:
result.append(cache[x])
else:
result.append(-1)
return result
``````

Condensed Code

``````class Solution(object):
def nextGreaterElement(self, findNums, nums):
"""
:type findNums: List[int]
:type nums: List[int]
:rtype: List[int]
"""
cache, st = {}, []
for x in nums:
while st and st[-1] < x:
cache[st.pop()] = x
st.append(x)
result = [-1]*len(findNums)
for idx,x in enumerate(findNums):
if x in cache:
result[idx] = cache[x]
return result
``````

• further condense without enumerate:

...st.append(x)

return [cache[num] if num in cache else -1 for num in nums]

• This post is deleted!

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