💬 Discord
Sign In
NeetCode #48LC-496EasyArrays & Hashing
← Back to All Problems

#48 · #496 · Next Greater Element I(下一个更大元素 I)

📌 Problem Statement & Constraints

You are given two arrays nums1 and nums2 where nums1 is a subset of nums2. For each element of nums1, find the first element to its right in nums2 that is greater than it. If none exists, use -1. Constraints: 1 <= nums1.length <= nums2.length <= 1000, all elements are distinct.

💡 Core Algorithmic Approaches

  1. The naive approach searches rightward in nums2 for each query, giving O(n * m).
  2. The classic solution is a monotonic decreasing stack over nums2: while the top of the stack is smaller than the current element, the current element is that top's next greater element.
  3. Record those pairs in a hash map from value to next-greater value.
  4. Then answer each query from nums1 with an O(1) map lookup, defaulting to -1.
  5. This is the template for the entire Next Greater Element family.

💻 Benchmark Python3 Implementation

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nxt = {}
        stack = []                         # monotonically decreasing values
        for x in nums2:
            while stack and stack[-1] < x:
                nxt[stack.pop()] = x       # x is the next greater element
            stack.append(x)
        # anything left on the stack has no greater element to its right
        return [nxt.get(v, -1) for v in nums1]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + m): each element of nums2 is pushed and popped at most once, and each query is an O(1) lookup.
💾 Space Complexity
O(m) for the stack and the map.

⚠️ Interview Pitfalls & Follow-ups

  • Using <= in the stack comparison: the elements are distinct here, so it does not matter, but for the general next-greater-or-equal variant the strictness changes the answer.
  • Popping without recording: every pop must write nxt[popped] = x; otherwise the answer is lost.
  • Forgetting the default -1: elements that never find a greater neighbour are absent from the map.
  • Searching nums2 from scratch for each query: O(n * m) and unnecessary.