> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/stack/mono-stack/496.-next-greater-element-i.md).

# 496. Next Greater Element I

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FKVAAFpBUBGUqj0d4ImYJ%2F%E5%9C%96%E7%89%87.png?alt=media\&token=88d05c8e-0ec3-4982-aefc-193516548d0d)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2F8XBfiRzipDWRsXSQkBzO%2F%E5%9C%96%E7%89%87.png?alt=media\&token=938a9328-6e24-4a0d-8cb3-8265f806ab8d)

## mono stack + hashmap

T: O(n+m), n is num1, m is nums2

T: O(n+m)

```java
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        
        Map<Integer, Integer> map = new HashMap<>(); // <number, next greater element>
        Deque<Integer> stack = new ArrayDeque<>();
        for (int num : nums2) {
            while (!stack.isEmpty() && num > stack.peek()) {
                int now = stack.pop();
                map.put(now, num);
            }
            stack.push(num);
        }
        
        int i = 0;
        for (int num : nums1) {
            res[i++] = map.getOrDefault(num, -1);
        }
        return res;
    }
    
}

/*

[1,3,4,2]
1: 3
3: 4
4: -1
2: -1



[4, 3, 2, 1, 6]

4: 6
3: 6
2: 6
1: 6
6: -1
*/
```