p52 — Next Greater Element I

Source: LeetCode 496 · Easy · Topics: Array, Hash Table, Stack, Monotonic Stack Companies (2024–2025 frequency): Amazon (high), Bloomberg (high), Meta (medium), Google (medium), Microsoft (medium) Loop position: Easy-tier warmup. Real signal: do you precompute on nums2 once and lookup in O(1)? Or do you naively scan for every query?

1. Quick Context

Two arrays:

  • nums1 is a subset of nums2. All values distinct within nums2.
  • For each nums1[i], find its next greater element in nums2 (look right of where it occurs in nums2). Return -1 if none.

The decomposition:

  1. Precompute next_greater[v] for every v in nums2 (one monotonic-stack pass).
  2. Lookup: ans[i] = next_greater[nums1[i]] (or -1).
nxt = {}                  # value -> next greater
stack = []                # values, monotonically decreasing
for v in nums2:
    while stack and stack[-1] < v:
        nxt[stack.pop()] = v
    stack.append(v)
for v in stack:           # no next greater
    nxt[v] = -1
return [nxt[v] for v in nums1]

Time O(n + m), space O(n). One pass.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/next-greater-element-i/

STOP. 8-min timer.

3. Prerequisite Concepts

  • Monotonic decreasing stack (p51).
  • Dict lookup as the “lookup” half of the precompute-then-lookup pattern.
  • The fact that nums2 has DISTINCT values lets us key by value rather than index.

4. How to Approach (FRAMEWORK Steps 1–9)

Step 1 — Restate: For each query value q in nums1, find its position in nums2, then the next strictly-greater value to the right; output -1 if none.

Step 2 — Clarify:

  • “Are values in nums2 distinct?” (Yes, per LC.)
  • “Strict greater or ≥?” (Strict.)
  • “Can nums1 contain a value not in nums2?” (No — nums1 ⊆ nums2.)
  • “Are values integers? Range?” (Yes, 0 ≤ v ≤ 10^4 typical.)

Step 3 — Constraints: Small (≤ 1000 each in LC). But O(n·m) brute would be slow on adversarial; aim for linear.

Step 4 — Examples:

  • nums1=[4,1,2], nums2=[1,3,4,2] → [-1,3,-1]
  • nums1=[2,4], nums2=[1,2,3,4] → [3,-1]
  • nums1=[1], nums2=[1] → [-1]

Step 5 — Brute: For each q, locate in nums2, scan right. O(n·m).

Step 6 — Complexity target: O(n + m).

Step 7 — Pattern: Precompute table via monotonic stack on nums2, then O(1) lookup per query in nums1.

Step 8 — Develop: see solution.py.

Step 9 — Test: subsets that miss, that hit, single-element, strictly increasing/decreasing nums2.

5. Progressive Hints

If stuck for 5 min, open hints.md.

6. Deeper Insight — Why “precompute once” matters

6.1 Two-phase decomposition

This problem is a textbook precompute / lookup decomposition:

  • Heavy work depends only on nums2 (one pass, O(m)).
  • Cheap work answers each nums1[i] query (O(1)).

If nums1 grew to a million queries and nums2 stayed at 1000, the precompute amortizes beautifully.

Anti-pattern (junior signal): “for each q in nums1, do a fresh scan/stack on nums2” — O(n·m) where the m-work is wasted. Recognize the decomposition out loud.

6.2 Why a dict (not an array)?

nums2 has distinct values; the precomputed table is keyed by value. A dict is the natural structure.

If values were bounded small ints (e.g., 0..10^4), you could use an array indexed by value — same asymptotic, slightly faster constant. Mention as a micro-optimization.

6.3 What if nums2 had duplicates?

Then “the value v” is ambiguous (multiple positions). You’d need to key by INDEX, not value, and nums1 would need to specify which occurrence — usually by passing indices.

This is exactly the setup of LC 503 (Next Greater II) when generalized.

6.4 Connection to p51 and p53

  • p51 (Daily Temperatures): same monotonic stack, returns distances by INDEX.
  • p52 (this): same stack, returns values via dict.
  • p53 (Next Greater II): same stack, circular — handle with 2n iteration.

One template, three flavors. Internalize the template.

6.5 Why decreasing (not increasing)?

We want greater as the resolution condition. The stack holds values waiting for someone greater. When a greater value arrives, it resolves them.

If we wanted smaller, we’d use a monotonic increasing stack with > pop condition.

7. Anti-Pattern Analysis

  1. For each q in nums1, run a fresh stack over nums2. O(n·m). Defeats the point.
  2. Build the stack but key by INDEX in nums2. Works, but then nums1[i] requires a value→index map first; just key by value directly.
  3. Use ≤ in the pop condition. Distinct values mean equality never happens; harmless here but a bad habit (breaks LC 503).
  4. Forget to default unresolved values to -1. Iterate remaining stack at end, or initialize the dict with -1 defaults.
  5. Sort either array. Destroys positional meaning. Don’t.
  6. Use a for j in range(i+1, len(nums2)) inside the precompute loop. That’s just brute force.
  7. Confuse “next greater than my value” with “next greater than my position.” They’re the same here because we lookup by value, but the FRAMING matters for harder variants.

8. Skills & Takeaways

  • The precompute-then-lookup decomposition.
  • Monotonic stack keyed by value when values are distinct.
  • Why distinct-values is a load-bearing assumption (lets us use a dict).
  • Connection to p51 / p53 — same template, three skins.

9. When to Move On

  • You can write the precompute-then-lookup in < 5 min cold.
  • You can explain why the dict is keyed by value (and what breaks if values weren’t distinct).
  • You can name the template (“monotonic decreasing stack, resolve on pop”) in one sentence.
  • Stress test on 1000 random distinct nums2 agrees with brute.

10. Company Context

Amazon:

  • L4/L5 OE. Warmup problem; the real signal is whether you do O(n+m) or O(n·m).
  • Bar Raiser: “Articulated the precompute/lookup decomposition without prompting.”

Bloomberg:

  • High-frequency for terminal/trading-floor SWE. Variant: “for each ticker, find next higher-volume tick” — same template.

Meta:

  • L4 screen. Mostly as a stepping stone to “now solve LC 503 (circular).”

Google:

  • L4. Often combined with a different pattern (e.g., “now apply to a stream”).

Microsoft:

  • L60-L62. Pair with LC 503 as the “harder version.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff/Principal
Decomposition“Loop over queries”“Precompute, I think”“Precompute on nums2 once”+ explains why dict key = value
Pattern“Stack”“Monotonic stack”“Monotonic decreasing stack of values”+ connects to p51 / p53
Distinct valuesIgnoresNotices when promptedNotes it lets us use a dict+ explains what breaks without distinctness
GeneralizationNone“Could probably use this elsewhere”Mentions circular variant (LC 503)+ sketches both LC 503 and previous-greater symmetry

12. Level Delta

Mid (L4):

  • Correct precompute-then-lookup.
  • Uses a dict.
  • Defaults missing to -1.

Senior (L5):

  • Articulates decomposition.
  • Notes the distinct-values dependency.
  • Mentions p51/p53 connection.

Staff (L6):

  • Discusses what changes if nums2 had duplicates (key by index, value→positions map).
  • Suggests bounded-int array optimization for small value ranges.
  • Discusses streaming variant (nums2 arrives over time, queries arrive interspersed).

Principal (L7+):

  • Discusses persistent monotonic stacks for the streaming variant where queries may ask “what was the next greater for value v as of time t?”
  • Discusses wavelet tree for general “next greater after position p with value > v” queries with updates.
  • Discusses cache locality — the stack approach has excellent locality vs. tree-based alternatives.

13. Follow-up Q&A

Q1: What if nums2 had duplicates? A1: Key the table by INDEX. Need a value→list-of-indices map for nums1 lookups. If nums1 also has duplicates, the problem becomes ill-defined without specifying which occurrence.

Q2: What if we wanted the next SMALLER element? A2: Flip to a monotonic INCREASING stack; pop while stack[-1] > v.

Q3: What if we wanted PREVIOUS greater (left side)? A3: Same template, but the answer for each pushed v is stack[-1] (the value below it after pops). I.e., resolve at PUSH for previous-greater.

Q4: What if nums2 was a stream? A4: Maintain the stack as values arrive; answer queries about already-popped values in O(1) (their answer is finalized). Queries about still-on-stack values must say “unknown yet.”

Q5: What’s the worst-case stack size? A5: m (strictly decreasing nums2 — nothing gets popped).

Q6: How does this relate to LC 503 (Next Greater II, circular)? A6: Iterate 2m instead of m, mod the index. First pass populates and may resolve; second pass only resolves (any still-unresolved after pass 2 truly has no answer).

14. Solution Walkthrough

See solution.py. Two implementations:

  • next_greater_element_stack — precompute via monotonic stack on nums2, lookup. O(n + m).
  • next_greater_element_brute — nested loop O(n·m) oracle.

Stress test on 1000 random distinct nums2 agrees.

15. Beyond the Problem

Principal-engineer code review comment:

“The dict-keyed-by-value pattern is fine for the LC-distinct-values case, but if you copy-paste this code into a production system where values aren’t distinct (e.g., stock prices that can repeat), you’ll get silent bugs — the dict overwrite hides them. Add an assert len(set(nums2)) == len(nums2) at the boundary, or rewrite to key by index from the start. The cost of the assertion is zero; the cost of the silent bug is hours of debugging.”