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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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 code in Java, Python, C++ and JavaScript.

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.
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).
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).