0496.Next Greater Element I

Link: 496. Next Greater Element I - Easy
Track: Amazon Tag

Question

Restate

• Give integer array nums1 and nums2
• num1 is num2 subset
• return num1 next greater if exist else -1

Edge Case

• nums2 = [4, 3, 2, 1], return [-1, -1, -1, -1]
• nums2 = [2, 2, 2, 2], return [-1, -1, -1, -1] won’t happen
  • if happened, use index in stack and add list = [-1] * n

---

Method 1 - monotonic stack (right to left) store large to small
Method 2 -brute force

Method 1 - Monotonic stack

Approach

use monotonic stack to store the large to small number

• Maintain a stack that is strictly decreasing (top is the nearest bigger candidate).

• Traverse nums2 from right to left:

  1. Pop all values <= current (they can’t be the next greater for current or any element to its left).
  2. After popping:
     • If stack is empty → nextGreater[current] = -1
     • Else → nextGreater[current] = stack[-1]
  3. Push current onto the stack.

• Q: Why traverse form right?

• next greater on the right

• A monotonic stack maintains valid candidates;

• After popping all values ≤ current, the stack top is the next greater element. This gives O(n) time.

Complexity

• Time Complexity: O(m + n)
  • m = len(nums1), n = len(nums2)
  • iterate nums2, take O(n)
  • result, take O(m)
• Space Complexity:
  • O(n)

Code

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        dic = {} # {val, next_greater_val}
        stack = []
        for num in reversed(nums2): 
            while stack and stack[-1] <= num:
                stack.pop()
            
            if stack:
                dic[num] = stack[-1]
            else:
                dic[num] = -1
            
            stack.append(num)
        
        # res = []
        # for num in nums1:
        #     res.append(dic[num])
        return [dic[num] for num in nums1]

Method 2 - Brute force

Complexity

• Time Complexity: O($n^2+m$)
  • m = len(nums1), n = len(nums2)
• Space Complexity:
  • O(n)

Code

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n = len(nums2)
        dic = {} 
        for i in range(n):
            for j in range(i + 1, n):
                if nums2[i] < nums2[j]:
                    dic[nums2[i]] = nums2[j]
                    break
            else:
                dic[nums2[i]] = -1
        
        return [dic[num] for num in nums1]

---

History

• Feb-17-2026 Peeked