LeetCode 496 Next Greater Element I - Example and Complexity Analysis

Trace nums2 = [1, 3, 4, 2].

Read 1: stack empty, push. Stack: [1].

Read 3: 3 > 1, pop 1, map 1 → 3. Push 3. Stack: [3].

Read 4: 4 > 3, pop 3, map 3 → 4. Push 4. Stack: [4].

Read 2: 2 < 4, just push. Stack: [4, 2].

End: 4 and 2 have no next greater.

Map: {1: 3, 3: 4}.

For nums1 = [4, 1, 2]: look up each. 4 → -1, 1 → 3, 2 → -1.

Process nums2 once: $O(n)$. Look up nums1 elements: $O(m)$. Total: $O(n + m)$ time. Map and stack: $O(n)$ space.