Next Greater Element I

Problem

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array. You are given two distinct 0-indexed integer arrays nums1 and nums2. For each element in nums1, find its next greater element in nums2.

Examples

The brute-force approach

For each element in nums1, find its position in nums2, then scan rightward through nums2 to find the first element larger than it.

answer = []

for x in nums1:
    idx = nums2.index(x)         # find x in nums2
    found = -1
    for j in range(idx + 1, len(nums2)):   # scan right
        if nums2[j] > x:
            found = nums2[j]
            break
    answer.append(found)

return answer

For each of the m elements in nums1 you may scan up to n elements of nums2. O(m × n) total. The next greater element for every value in nums2 can be computed in a single O(n) pass using a monotonic stack. Then answering queries for nums1 is just a hash map lookup. O(1) per element.

Spotting the pattern

This is a Stack problem. The key question to ask yourself:

How do I find the next greater element for every value in nums2 without scanning right from each position?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.