Next Greater Element I

Easy· monotonic stack· next greater

Problem

nums1 is a subset of nums2, and all values are distinct. For each value in nums1, find where it sits in nums2 and report the first value to its right that is larger, or -1 if none exists.

Examples

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]

Output: [-1,3,-1]

Nothing larger follows 4 or 2; 3 is the first larger value after 1.

Input: nums1 = [2,4], nums2 = [1,2,3,4]

Output: [3,-1]

Constraints

• 1 <= nums1.length <= nums2.length <= 1000
• All values are unique
• Every value of nums1 appears in nums2

Hints & approach

Hint 1

Compute the next greater element for every value in nums2 once, then look up answers.

Hint 2

Keep a stack of values still waiting for a larger one.

Hint 3

When a new value arrives, it is the answer for every smaller value on top of the stack.

Approachtry the hints first

Scan nums2 while keeping a stack whose values decrease from bottom to top; these are the values that have not yet seen a larger element. For each new value x, pop every smaller value v and record next[v] = x, then push x. Values left on the stack at the end have no greater element. Finally map each value in nums1 through the dictionary, defaulting to -1.

Time O(n + m) · Space O(m)

Next →Daily Temperatures