next-greater-element-i

Difficulty: Easy  ·  Topic: Stack  ·  Practice it on parikshan: /practice/next-greater-element-i/start

The story

A trading-research team at Renaissance Technologies asks: given a watch-list of stock tickers (nums1) and a reference universe of tickers in their daily-volume order (nums2), report, for each ticker on the watch-list, the volume of the next ticker in the reference universe that traded a higher daily volume. If no such ticker exists, report -1. The watch-list and the universe are guaranteed to be a subset relationship: every watch-list ticker appears in the universe, all values are distinct.

That is next-greater-element-i. It is the easy version of the monotonic-stack family, with a tiny indirection: the answers are reported for a subset of values, but the computation happens on the full reference array.

What's actually being asked

Given two arrays nums1 (length n) and nums2 (length m) with n <= m, where nums1 is a subset of nums2 and elements within each are distinct, for each value x in nums1, find the first value to the right of x in nums2 that is strictly greater than x. If none exists, return -1. Print the answers for nums1, in order.

The naive approach

For each x in nums1, find x in nums2, then scan rightward for the first greater. O(n * m). For n = m = 10^5, that is 10 billion. Times out.

The key insight

Compute the "next greater" for every element of nums2 once, store it in a hash map from value to its next-greater (or to -1), and then look up each value of nums1 in O(1). The "next greater for every element" computation is the canonical monotonic-stack pattern.

Two clean ways to do the stack pass:

1. Left-to-right with a decreasing stack of values (since values are distinct, we can store values directly): as we visit nums2[i], pop stack values that are < nums2[i]; each pop's "next greater" is nums2[i]. Push nums2[i]. After the pass, any value still on the stack has next-greater = -1.

2. Right-to-left with a decreasing stack of values: standard right-to-left "next greater". Same time complexity, mirror-image code.

Either way: O(m) to build the map, O(n) to answer. Total O(n + m).

Step-by-step approach

1. next_greater = {} (will map value to its next-greater value).
2. stack = [] (will hold values, since values are distinct).
3. For each v in nums2:
   • While stack is non-empty and stack[-1] < v:
     • next_greater[stack.pop()] = v.
   • Push v onto stack.
4. For any value still on stack: next_greater[value] = -1 for each.
5. For each x in nums1, append next_greater[x] to the answer.
6. Print the answer.

Worked example

nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]

Pass over nums2:

Cleanup: stack has [4, 2]. next_greater[4] = -1, next_greater[2] = -1.

Final map: {1:3, 3:4, 4:-1, 2:-1}.

Answer for nums1:

• 4 -> -1
• 1 -> 3
• 2 -> -1

Output: -1 3 -1.

Complexity

• Time: O(n + m).
• Space: O(m) for the stack and map.

The brute force is O(n * m). The monotonic stack converts the inner search into amortised constant time.

Common pitfalls

• Iterating nums1 and rescanning nums2 for each: O(n * m). The hash-map indirection is the optimisation.
• Using a stack of indices when values are distinct: works but adds indirection. Since the spec promises distinct values, a stack of values is cleaner.
• Using <= instead of < on the comparison: <= would pop on equal values, but the spec promises distinct, so it doesn't matter here. In the generalised version (next-greater-element-ii, where duplicates can appear in the circular array), the choice matters; pick <= if you want "strictly greater" and < if you want "greater or equal".
• Forgetting the leftover-stack cleanup: values still on the stack at the end have no next greater. Assign them -1. Many candidates write the loop and then forget this step.
• Returning answers in the wrong order: the spec says answers are for nums1 in its order, not in nums2's order.

Where this shows up in the enterprise

• Trading platforms (Renaissance, Citadel, Bloomberg): "next higher volume / price tick" lookups across reference universes.
• Search ranking (Google, Bing): "next more-relevant result" lookups across pre-ranked indices.
• Database query optimisers (Snowflake, BigQuery): "next higher-cardinality column" lookups during plan exploration.
• Spreadsheet auditing (Excel, Google Sheets): "next higher value in this column" queries for outlier detection.
• AdTech bid landscapes: "next higher CPM bidder" lookups across auction logs.
• GitHub repo analytics: "next more-starred sibling repo" lookups.
• CDN log analysis: "next higher response-time entry" lookups for tail-latency studies.
• Robotics path planning: "next obstacle of greater height" lookups along a profile.

The pattern is: lookup the closest-rightward element exceeding a value, applied across many queries. Precompute once with a stack, answer each query in O(1).

Variants you'll see elsewhere

• next-greater-element-ii: nums2 is circular (wrap-around). Same algorithm, walk the array twice.
• next-greater-element-iii: a misnomer; it is a permutation problem, not a stack problem.
• daily-temperatures: same pattern, return distances.
• online-stock-span: same pattern as a streaming online API.
• largest-rectangle-in-histogram: uses both next-smaller-right and next-smaller-left.
• 132-pattern: monotonic stack on a more complex predicate.

How parikshan turns this into a learning loop

The dynamic private tests on parikshan cover:

• nums1 == nums2 (full reference universe).
• nums1 is the first element of nums2.
• nums1 is the last element of nums2 (always -1).
• A nums2 that is strictly increasing (every element has a next greater).
• A nums2 that is strictly decreasing (every element except the last has no next greater).
• Many queries (n close to m), forcing the hash-map indirection to be useful.

The integrity-scored AI sparring partner is the place, in practice mode, to verbalise the monotonic-stack invariant ("the stack holds values in strictly decreasing order; any value smaller than the current one is resolved by the current one") before writing the code in exam mode.

In the AI-integrated workspace

When an agent writes "next greater" lookups, your review checks:

1. Is there a single linear pass over the reference array, or is the agent repeating the scan per query?
2. Is the lookup structure a hash map keyed by value (correct, given distinct values) or by index (over-complicated)?
3. Are leftover stack values assigned -1, not silently omitted?
4. Does the algorithm handle the case where nums1 is empty? (The map is still built; the answer is just empty.)

The monotonic-stack reflex from daily-temperatures carries over directly. The only new wrinkle here is the subset-of-queries indirection through a hash map. Once you internalise "precompute next-greater for all, look up the subset", the variant becomes a natural composition.

next-greater-element-i is the lightest weight monotonic-stack problem in the cluster. Solve it on parikshan in under three minutes once you have done daily-temperatures, and you have the pattern locked in for the harder variants.