• 1 <= nums1.length <= nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 10⁴
• All integers in nums1 and nums2 are unique
• nums1 is a subset of nums2

For each number, we want the first number to its right that is strictly bigger. The obvious way is to stand on a number and walk rightward until something larger turns up. On a run like [5, 4, 3, 2, 1] that walk restarts from scratch every time: the 5 scans past 4, 3, 2, 1, then the 4 scans past 3, 2, 1 again, and so on — roughly N²/2 comparisons, all re-reading the same tail nobody bothered to remember.

So let's remember — but remember the useful thing. Picture scanning left to right while holding the numbers that are still waiting for their answer. Claim: those waiting numbers are always in decreasing order from bottom to top. Why must that be true? A number only keeps waiting while nothing bigger has appeared yet. The moment a bigger number shows up, the waiting number's answer is found and it stops waiting. So if you ever had a small number sitting on top of... no — if a newer waiting number were bigger than an older one beneath it, that newer number would already have answered and removed the older one on its way in. Whatever is left can only go downhill.

That structure — a stack whose values are kept sorted, where the instant the order is about to break you've discovered someone's answer — is a monotonic stack. It's just an ordinary stack (push and pop at one end) with the extra rule that its contents stay in order. Here we keep them decreasing.

Walk nums2 from left to right. The current number challenges the top of the stack: while the top is smaller than the current number, the current number is exactly that top's next-greater element — record it, pop it, and keep going, because one big number can clear out a whole run of smaller ones waiting beneath it. When the top is finally bigger (or the stack is empty), push the current number so it can wait for its own answer. Since nums1 is a subset of nums2, answer all of nums2 into a map first, then read off the queries.

# Monotonic Stack (O(N + M) Time, O(M) Space)
stack = []
next_greater = {}

for num in nums2:
    # every number smaller than 'num' still on the stack just found its answer
    while stack and num > stack[-1]:
        next_greater[stack.pop()] = num
    stack.append(num)          # now 'num' waits for something bigger

return [next_greater.get(x, -1) for x in nums1]

The while-loop looks like it could make this quadratic, but it can't: every number is pushed once and popped at most once, so across the whole run there are at most M pops total. That's the real payoff of the monotonic stack — the nested loop is an illusion, the work is linear. Anything still on the stack at the end never met a bigger number, so its answer is -1.

Reach for a monotonic stack whenever a problem asks, for every position, about the nearest element in some direction that is bigger or smaller than it — "next greater element", "previous smaller", "how many days until a warmer one", "how far a bar can stretch before a shorter one". Two tells give it away: a brute force would re-scan the same neighbors over and over, and an element becomes permanently useless the moment a better one appears past it (that's what makes it safe to pop and forget). Keep the stack increasing when you're hunting for smaller neighbors and decreasing when hunting for larger ones; the direction you scan chooses which side's neighbor you find.