Next Greater Element I

LeetCode 496 · View on LeetCode

Given nums1 (a subset of nums2), for each element in nums1 find the first element to its right in nums2 that is larger. Return -1 if none exists.

Solution 1: Monotonic Stack + Map — O(n)

Process nums2 with a decreasing stack. When an element pops something off the stack, it's the next greater for that popped value. Store results in a map for O(1) lookup.

package main

import "fmt"

func nextGreaterElement(nums1 []int, nums2 []int) []int {
	nextGreater := map[int]int{}
	stack := []int{} // decreasing stack of values

	for _, n := range nums2 {
		for len(stack) > 0 && n > stack[len(stack)-1] {
			nextGreater[stack[len(stack)-1]] = n
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, n)
	}

	result := make([]int, len(nums1))
	for i, n := range nums1 {
		if val, ok := nextGreater[n]; ok {
			result[i] = val
		} else {
			result[i] = -1
		}
	}
	return result
}

func main() {
	fmt.Println(nextGreaterElement([]int{4, 1, 2}, []int{1, 3, 4, 2})) // [-1 3 -1]
	fmt.Println(nextGreaterElement([]int{2, 4}, []int{1, 2, 3, 4}))    // [3 -1]
}

Time: O(n + m) — each element in nums2 is pushed and popped at most once, then one pass through nums1. Space: O(n) — stack + map.

Solution 2: Brute Force — O(n·m)

For each element in nums1, find it in nums2, then scan right for the first larger value.

package main

import "fmt"

func nextGreaterElement(nums1 []int, nums2 []int) []int {
	result := make([]int, len(nums1))
	for i, n := range nums1 {
		result[i] = -1
		found := false
		for _, m := range nums2 {
			if m == n {
				found = true
			} else if found && m > n {
				result[i] = m
				break
			}
		}
	}
	return result
}

func main() {
	fmt.Println(nextGreaterElement([]int{4, 1, 2}, []int{1, 3, 4, 2})) // [-1 3 -1]
	fmt.Println(nextGreaterElement([]int{2, 4}, []int{1, 2, 3, 4}))    // [3 -1]
}

Time: O(n·m) — for each element in nums1, scan through nums2. Space: O(1) — only the result array.

Comparison

Approach	Time	Space	Notes
Monotonic stack	O(n + m)	O(n)	Optimal. Each element pushed/popped once
Brute force	O(n·m)	O(1)	Simple but slow for large inputs