Next Greater Element I

Next Greater Element I

What is this problem about?

The Next Greater Element I problem gives you two arrays, nums1 and nums2, where nums1 is a subset of nums2. For each element in nums1, find the next greater element that appears to its right in nums2. Return -1 if no greater element exists. This Next Greater Element I coding problem is the foundational monotonic stack problem.

Why is this asked in interviews?

Apple, Uber, Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, and many others ask this as the entry point to the monotonic stack pattern. It validates that candidates understand how a decreasing stack works for "next greater" queries. The array, monotonic stack, hash table, and stack interview pattern is the cornerstone here.

Algorithmic pattern used

Monotonic decreasing stack + hash map. Process nums2 left to right. Maintain a stack of elements for which we haven't found the next greater yet. For each element x: while the stack top is less than x, the stack top's next greater is x — pop and record in a hash map. Push x onto the stack. After processing, elements remaining on stack have no next greater (-1). Look up each nums1 element in the hash map.

Example explanation

nums2 = [4, 1, 2, 3]. Process:

• Push 4. Stack: [4].
• Push 1. Stack: [4,1].
• 2 > 1 → pop 1, map[1]=2. 2 < 4 → push 2. Stack: [4,2].
• 3 > 2 → pop 2, map[2]=3. 3 < 4 → push 3. Stack: [4,3].
• Remaining [4,3]: map[4]=-1, map[3]=-1.

nums1=[1,4]: answers = [map[1]=2, map[4]=-1] = [2, -1].

Common mistakes candidates make

• Using a sorted/min stack instead of a decreasing (next-greater) stack.
• Processing nums1 directly instead of building the map from nums2.
• Off-by-one: popping when stack.top() < x vs ≤ x (strict vs non-strict greater).
• Building the map using a linear search per nums1 element (O(n*m) vs O(n+m)).

Interview preparation tip

The monotonic stack for "next greater element" follows a consistent template: iterate left-to-right, maintain a decreasing stack, pop-and-record when current element exceeds the stack top. Memorize this template and practice it for all four variants: next greater, next smaller, previous greater, previous smaller. These four patterns cover the majority of monotonic stack interview questions. Practice until the stack operations feel automatic.