Start practising

Next Greater Element I

Easy Monotonic Stack Monotonic Stack Original on LeetCode

Next Greater Element I is a easy monotonic stack problem solved with the monotonic stack pattern. The best approach, optimal (monotonic stack + map), runs in O(m + n) time and O(n) space. Below are 2 approaches in Java, from brute force up.

Problem

For each value x in nums1, find where x appears in nums2 and return the first larger value to its right in nums2, or -1 if there is none. All values are distinct and nums1 is a subset of nums2.

Examples

Example 1

Input
nums1 = [2, 5], nums2 = [3, 2, 7, 5]
Output
[7, -1]
Why
After 2 in nums2 comes 7. Nothing greater follows 5.

Example 2

Input
nums1 = [1], nums2 = [1, 4]
Output
[4]

Constraints

  • 1 <= nums1.length <= nums2.length <= 1000
  • All values are distinct; nums1 is a subset of nums2.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Brute forceO(m · n)O(1)
Optimal (monotonic stack + map)O(m + n)O(n)

1Brute force

TimeO(m · n)
SpaceO(1)

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

  1. Locate x in nums2.
  2. Scan to the right for the first value > x.
Java
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] out = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            out[i] = -1;
            int j = 0;
            while (nums2[j] != nums1[i]) j++;
            for (j++; j < nums2.length; j++)
                if (nums2[j] > nums1[i]) { out[i] = nums2[j]; break; }
        }
        return out;
    }
}

2Optimal (monotonic stack + map)

TimeO(m + n)Each value is pushed and popped once.
SpaceO(n)

Scan nums2 keeping a stack of values still waiting for a greater element; it stays decreasing. When a larger value arrives, it is the answer for every smaller value it pops. Store answers in a map and look up nums1.

  1. For each x in nums2: while stack top < x, map[pop()] = x. Push x.
  2. out[i] = map.getOrDefault(nums1[i], -1).
Java
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> next = new HashMap<>();
        Deque<Integer> st = new ArrayDeque<>();
        for (int x : nums2) {
            while (!st.isEmpty() && st.peek() < x) next.put(st.pop(), x);
            st.push(x);
        }
        int[] out = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) out[i] = next.getOrDefault(nums1[i], -1);
        return out;
    }
}

Edge cases to test

  • The last element of nums2 (always -1)
  • A decreasing nums2 (all -1)

Hints

Hint 1

Compute the next greater element for every value of nums2 once, then look them up.

FAQ

What is the best time complexity for Next Greater Element I?

Optimal (monotonic stack + map) runs in O(m + n) time and O(n) extra space. Each value is pushed and popped once.

Which pattern does Next Greater Element I use?

It is a monotonic stack problem that uses the monotonic stack pattern. Other problems with the same pattern: Daily Temperatures, Next Greater Element II, Largest Rectangle in Histogram.

Is there a brute force solution for Next Greater Element I?

Yes. Brute force takes O(m · n) time and O(1) space. For each value of nums1, find it in nums2 and scan right for the first larger value.

Which edge cases should I test for Next Greater Element I?

The last element of nums2 (always -1); A decreasing nums2 (all -1).