Hints — p52 Next Greater Element I

Hint 1. The naive approach — “for each q in nums1, locate it in nums2, scan right” — is O(n·m). The whole point of the problem is to recognize you can do better.

Hint 2. Reframe: decouple the work that depends only on nums2 from the work that depends on nums1. Build a table once over nums2; then each nums1[i] is an O(1) lookup.

Hint 3. The table is “for each value v in nums2, what’s its next greater value?” — and this is a monotonic-stack problem identical in shape to p51 Daily Temperatures.

Hint 4. Since nums2 has DISTINCT values, key the table by value (dict), not by index. Then ans[i] = table.get(nums1[i], -1).

Hint 5. After the loop ends, any value left on the stack has no next-greater. Either pre-default the dict to -1, or sweep the remaining stack and assign -1.

If still stuck: see solution.py.