Next Greater Element I

Start dumb: search to the right, every time

For each value in nums1, find where it lives in nums2, then walk right until you hit something bigger. Two nested scans over nums2 — O(n·m), and worse, most of that walking is repeated: the same stretch of nums2 gets re-scanned for every query that lands near it.

Find the bottleneck

The waste is that each query rediscovers the same “next bigger number to the right” from scratch. But that relationship doesn’t depend on nums1 at all — it’s a fixed property of nums2. Compute it once for every element of nums2, cache it, and the nums1 queries become one lookup each.

The optimal shape

1. For each num in nums2, while the stack’s top is smaller than num, pop it — num is that popped value’s next-greater. Record it in a value → nextGreater map.
2. Push num; it now waits for its own bigger number.
3. Anything still on the stack at the end never found one — its answer is −1.
4. Each nums1 query is a single map lookup (default −1).

In the player, the stack is the highlighted run of nums2; watch one big number clear a whole backlog of waiters in consecutive steps.

Watch it think

Run the default, then the traps: a lone big number answering a backlog of three (4,3,2 | 4,3,2,5), a strictly falling nums2 where every answer is −1 (5,4,3 | 5,4,3,2,1), and a strictly climbing one where each number is answered by the very next (2,4 | 1,2,3,4).

1fun nextGreaterElement(nums1: IntArray, nums2: IntArray): IntArray {
2    val nextGreater = HashMap<Int, Int>()
3    val stack = ArrayDeque<Int>()
4    for (num in nums2) {
5        while (stack.isNotEmpty() && stack.last() < num) {
6            nextGreater[stack.removeLast()] = num
7        }
8        stack.addLast(num)
9    }
10    return IntArray(nums1.size) { i -> nextGreater[nums1[i]] ?: -1 }
11}