Next Greater Element I

Easy Problem 34 of 151 Java and Python

Problem

The next greater element of a number x in an array is the first number to the right of x that is larger than x.

You are given two arrays of distinct integers, nums1 and nums2, where nums1 is a subset of nums2. For each nums1[i], find its next greater element **in nums2**, or -1 if there is none. Return the answers in order.

Example 1

Input: nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]
Output: [-1, 3, -1]
Why: Nothing after 4 is larger; after 1 comes 3; nothing after 2.

Example 2

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

Constraints

1 ≤ nums1.length ≤ nums2.length ≤ 1000
All values are unique, and every value of nums1 is in nums2.

Explanation

Compute the next greater element for every number in nums2 once, store the results in a map, then just look up each number of nums1.

Walk nums2 with a stack of numbers still waiting for a bigger one. When a bigger number arrives, it is the answer for everything smaller on top of the stack.

Approach 1 · Naive

Find, then scan right

Time O(m · n)
Space O(1) besides the output

For each number in nums1, find it in nums2 and scan to the right for the first larger value.

For each x in nums1, find its index j in nums2.
Scan nums2[j + 1 …] for the first value greater than x; default to -1.

Java

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = -1;
            boolean found = false;
            for (int num : nums2) {
                if (num == nums1[i]) {
                    found = true;
                } else if (found && num > nums1[i]) {
                    result[i] = num;
                    break;
                }
            }
        }
        return result;
    }
}

Python

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = []
        for x in nums1:
            j = nums2.index(x)
            greater = next((y for y in nums2[j + 1:] if y > x), -1)
            result.append(greater)
        return result

Approach 2 · Optimal

Monotonic stack + map

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

Keep a stack of numbers in decreasing order. Each new number pops every smaller number and becomes their next greater element.

For each num in nums2: while the stack top is smaller than num, pop it and record next[top] = num. Push num.
Answer each x in nums1 with next.get(x, -1).

Java

import java.util.*;

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> next = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();
        for (int num : nums2) {
            while (!stack.isEmpty() && stack.peek() < num) {
                next.put(stack.pop(), num);
            }
            stack.push(num);
        }
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = next.getOrDefault(nums1[i], -1);
        }
        return result;
    }
}

Python

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nxt = {}
        stack = []
        for num in nums2:
            while stack and stack[-1] < num:
                nxt[stack.pop()] = num
            stack.append(num)
        return [nxt.get(x, -1) for x in nums1]

Complexity compared

Approach	Time	Space
Naive Find, then scan right	O(m · n)	O(1) besides the output
Optimal Monotonic stack + map	O(m + n)	O(n)

Key takeaways

"Next greater / smaller element" is the textbook monotonic stack pattern; Daily Temperatures is the same problem with distances.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem