← Stacks & Queues

Next Greater Element

Medium
Python
def next_greater_element(nums1,nums2):
    ng={}; stack=[]
    for n in nums2:
        while stack and stack[-1]<n: ng[stack.pop()]=n
        stack.append(n)
    return [ng.get(n,-1) for n in nums1]
Java
public int[] nextGreaterElement(int[] nums1,int[] nums2){
    Map<Integer,Integer> ng=new HashMap<>();
    Stack<Integer> stack=new Stack<>();
    for(int n:nums2){
        while(!stack.isEmpty()&&stack.peek()<n) ng.put(stack.pop(),n);
        stack.push(n);
    }
    int[] res=new int[nums1.length];
    for(int i=0;i<nums1.length;i++) res[i]=ng.getOrDefault(nums1[i],-1);
    return res;
}

Key Insight

Python list comprehension for result. dict.get() vs getOrDefault().

Python → Java Differences

  • List comprehension for result
  • dict.get(n,-1) vs getOrDefault()
  • Monotonic stack identical
Python
def next_greater_element(nums1,nums2):
    ng={}; stack=[]
    for n in nums2:
        while stack and stack[-1]<n: ng[stack.pop()]=n
        stack.append(n)
    return [ng.get(n,-1) for n in nums1]
Java
public int[] nextGreaterElement(int[] nums1,int[] nums2){
    Map<Integer,Integer> ng=new HashMap<>();
    Stack<Integer> stack=new Stack<>();
    for(int n:nums2){
        while(!stack.isEmpty()&&stack.peek()<n) ng.put(stack.pop(),n);
        stack.push(n);
    }
    int[] res=new int[nums1.length];
    for(int i=0;i<nums1.length;i++) res[i]=ng.getOrDefault(nums1[i],-1);
    return res;
}

Algorithm Steps

1. Build next-greater map
2. Look up nums1
← Previous All Stacks & Queues Next →