496. Next Greater Element I

LeetCode Problem Link (opens new window)

You are given two arrays nums1 and nums2 without duplicate elements, where nums1 is a subset of nums2.

For each element in nums1, find the next greater element in nums2.

The next greater element of a number x in nums1 is the first greater number to the right of x in nums2. If it does not exist, output -1 for this position.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
For number 4 in num1, you cannot find a greater number in the second array, so the output is -1.
For number 1 in num1, the next greater number to the right of it in the second array is 3.
For number 2 in num1, there is no greater number in the second array, so the output is -1.

Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
For number 2 in num1, the next greater number in the second array is 3.
For number 4 in num1, there is no greater number, so the output is -1.

Constraints:

• 1 <= nums1.length <= nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 10^4
• All integers in nums1 and nums2 are unique
• All integers in nums1 also appear in nums2

Thought Process

Before solving this problem, it is recommended to solve 0739. Daily Temperatures (opens new window).

In 0739. Daily Temperatures (opens new window), the task was to find the next greater element's position for each element.

In this problem, nums1 is a subset of nums2, and you need to find the next greater element in nums2 for the elements in nums1.

It appears quite similar to 0739. Daily Temperatures (opens new window), with a slight increase in complexity.

To solve this problem effectively, you must be very proficient with the use of monotonic stacks.

From the examples provided in the problem statement, the final goal is to determine each element's next greater counterpart in nums2 for elements in nums1. Hence, you need a result array of the same size as nums1 to store the result.

How to define and initialize this result array?

The problem states that if there is no next greater element, output -1. Hence, the result array should be initialized to -1 if no assignment is made to a position.

While iterating through nums2, you need to check if nums2[i] has appeared in nums1, because the result needs to be updated based on nums1's index.

Note that the problem states that both arrays consist of unique elements.

Given that, a map can be used for efficient element index lookup. Moreover, it helps to quickly determine whether nums2[i] has appeared in nums1.

In C++, when using a collection for hashing purposes, prioritize using unordered_set as it offers optimal query and manipulation performance. This has been explained in detail under Hash Table Basics (opens new window).

The preprocessing code is as follows:

unordered_map<int, int> umap; // key: element, value: index
for (int i = 0; i < nums1.size(); i++) {
    umap[nums1[i]] = i;
}

When using a monotonic stack, first determine whether it should be maintained from large to small or from small to large.

This problem is equivalent to 739. Daily Temperatures, and hence the stack should be maintained in increasing order from the stack head to the base. Only by maintaining an increasing order can we find the next greater element on the right.

For any doubts, try using a decreasing stack to see if it solves the problem. A decreasing stack will lead to finding the next smaller element on the right.

Now, let's analyze three scenarios:

1. Scenario 1: Current element nums2[i] is less than the stack's top element nums2[st.top()].

In this scenario, an increasing order is maintained (stack head to base), so push onto the stack.

2. Scenario 2: Current element nums2[i] is equal to the stack's top element nums2[st.top()].

Even if equal, still push onto the stack, since we are searching for strictly greater numbers, not greater or equal.

3. Scenario 3: Current element nums2[i] is greater than the stack's top element nums2[st.top()].

If inserted, the stack will no longer maintain an increasing order, so we have found the next greater element on the right side.

Check if the stack's top element appears in nums1 (remember that elements in the stack are elements of nums2). Once confirmed, start recording results.

In this part, the logic is a bit convoluted. Be clear that nums2[i] (the current element being iterated) is the next greater element to the right of the stack's top element.

Here is the code:

while (!st.empty() && nums2[i] > nums2[st.top()]) {
    if (umap.count(nums2[st.top()]) > 0) { // Check if the element exists in the map
        int index = umap[nums2[st.top()]]; // Find the index of nums2[st.top()] in nums1 using the map
        result[index] = nums2[i];
    }
    st.pop();
}
st.push(i);

The above analysis is complete, with the C++ code shown below (essentially similar to 0739. Daily Temperatures (opens new window)):

// Version 1
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        vector<int> result(nums1.size(), -1);
        if (nums1.size() == 0) return result;

        unordered_map<int, int> umap; // key: element, value: index
        for (int i = 0; i < nums1.size(); i++) {
            umap[nums1[i]] = i;
        }
        st.push(0);
        for (int i = 1; i < nums2.size(); i++) {
            if (nums2[i] < nums2[st.top()]) {           // Scenario 1
                st.push(i);
            } else if (nums2[i] == nums2[st.top()]) {   // Scenario 2
                st.push(i);
            } else {                                    // Scenario 3
                while (!st.empty() && nums2[i] > nums2[st.top()]) {
                    if (umap.count(nums2[st.top()]) > 0) { // Check if the element exists in the map
                        int index = umap[nums2[st.top()]]; // Find the index of nums2[st.top()] in nums1 using the map
                        result[index] = nums2[i];
                    }
                    st.pop();
                }
                st.push(i);
            }
        }
        return result;
    }
};

Here's a more concise version of the code from Version 1:

// Version 2
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        vector<int> result(nums1.size(), -1);
        if (nums1.size() == 0) return result;

        unordered_map<int, int> umap; // key: element, value: index
        for (int i = 0; i < nums1.size(); i++) {
            umap[nums1[i]] = i;
        }
        st.push(0);
        for (int i = 1; i < nums2.size(); i++) {
            while (!st.empty() && nums2[i] > nums2[st.top()]) {
                if (umap.count(nums2[st.top()]) > 0) { // Check if the element exists in the map
                    int index = umap[nums2[st.top()]]; // Find the index of nums2[st.top()] in nums1 using the map
                    result[index] = nums2[i];
                }
                st.pop();
            }
            st.push(i);
        }
        return result;
    }
};

While the simplified code consolidates all scenarios into one, it's less clear. It's advisable to understand scenarios 1, 2, and 3 thoroughly and implement Version 1 first, then proceed to simplify the code!

Versions in Other Languages

C

/* First calculate results using the monotonic stack method, then find the corresponding results based on elements in nums1 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {

    /* stack */
    int top = -1;
    int stack_len = nums2Size;
    int stack[stack_len];
    //memset(stack, 0x00, sizeof(stack));

    /* nums2 result */
    int* result_nums2 = (int *)malloc(sizeof(int) * nums2Size);
    //memset(result_nums2, 0x00, sizeof(int) * nums2Size);

    /* result */
    int* result = (int *)malloc(sizeof(int) * nums1Size);
    //memset(result, 0x00, sizeof(int) * nums1Size);
    *returnSize = nums1Size;

    /* init */
    stack[++top] = 0; /* stack loaded with array subscripts */

    for (int i = 0; i < nums2Size; i++) {
        result_nums2[i] = -1;
    }

    /* get the result_nums2 */
    for (int i = 1; i < nums2Size; i++) {
        if (nums2[i] <= nums2[stack[top]]) {
            stack[++top] = i; /* push */
        } else {
            while ((top >= 0) && (nums2[i] > nums2[stack[top]])) {
                result_nums2[stack[top]] = nums2[i];
                top--; /* pop */
            }
            stack[++top] = i;
        }
    }

    /* get the result */
    for (int i = 0; i < nums1Size; i++) {
        for (int j = 0; j < nums2Size; j++) {
            if (nums1[i] == nums2[j]) {
                result[i] = result_nums2[j];
            }
        }
    }
    return result;
}

Java

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> temp = new Stack<>();
        int[] res = new int[nums1.length];
        Arrays.fill(res,-1);
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0 ; i< nums1.length ; i++){
            hashMap.put(nums1[i],i);
        }
        temp.add(0);
        for (int i = 1; i < nums2.length; i++) {
            if (nums2[i] <= nums2[temp.peek()]) {
                temp.add(i);
            } else {
                while (!temp.isEmpty() && nums2[temp.peek()] < nums2[i]) {
                    if (hashMap.containsKey(nums2[temp.peek()])){
                        Integer index = hashMap.get(nums2[temp.peek()]);
                        res[index] = nums2[i];
                    }
                    temp.pop();
                }
                temp.add(i);
            }
        }

        return res;
    }
}

// Version 2
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            map.put(nums1[i], i);
        }

        int[] res = new int[nums1.length];
        Stack<Integer> stack = new Stack<>();
        Arrays.fill(res, -1);

        for (int i = 0; i < nums2.length; i++) {
            while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {
                int pre = nums2[stack.pop()];
                if (map.containsKey(pre)) {
                    res[map.get(pre)] = nums2[i];
                }
            }
            stack.push(i);
        }

        return res;
    }
}

Python3

# Version 1
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = [-1]*len(nums1)
        stack = [0]
        for i in range(1,len(nums2)):
            # Scenarios 1 and 2
            if nums2[i]<=nums2[stack[-1]]:
                stack.append(i)
            # Scenario 3
            else:
                while len(stack)!=0 and nums2[i]>nums2[stack[-1]]:
                    if nums2[stack[-1]] in nums1:
                        index = nums1.index(nums2[stack[-1]])
                        result[index]=nums2[i]
                    stack.pop()                 
                stack.append(i)
        return result

# Version 2
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        # Create the answer array
        ans = [-1] * len(nums1)
        for i in range(len(nums2)):
            while len(stack) > 0 and nums2[i] > nums2[stack[-1]]:
                # Check if nums1 contains nums2[stack[-1]]. Without this, there can be a pointer exception.
                if nums2[stack[-1]] in nums1:
                    # Lock the index in nums1 for search
                    index = nums1.index(nums2[stack[-1]])
                    # Update the answer array
                    ans[index] = nums2[i]
                # Pop smaller elements
                # This code must be outside the if, otherwise, the logic of the monotonic stack does not hold.
                stack.pop()
            stack.append(i)
        return ans

Go

Unrefined Version

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    res := make([]int, len(nums1))
    for i := range res { res[i] = -1 }
    m := make(map[int]int, len(nums1))
    for k, v := range nums1 { m[v] = k }

    stack := []int{0}
    for i := 1; i < len(nums2); i++ {
        top := stack[len(stack)-1]
        if nums2[i] < nums2[top] {
            stack = append(stack, i)
        } else if nums2[i] == nums2[top] {
            stack = append(stack, i)
        } else {
            for len(stack) != 0 && nums2[i] > nums2[top] {
                if v, ok := m[nums2[top]]; ok {
                    res[v] = nums2[i]
                }
                stack = stack[:len(stack)-1]
                if len(stack) != 0 {
                    top = stack[len(stack)-1]
                }
            }
            stack = append(stack, i)
        }
    }
    return res
}

Refined Version

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    res := make([]int, len(nums1))
    for i:= range res {
        res[i] = -1
    }
    mp := map[int]int{}
    for i,v := range nums1 {
        mp[v] = i
    }
    // Monotonic stack
    stack := []int{}
    stack = append(stack,0)

    for i:=1; i<len(nums2); i++ {
        for len(stack) >0 && nums2[i] > nums2[stack[len(stack)-1]] {

            top := stack[len(stack)-1]

            if _, ok := mp[nums2[top]]; ok {    // Check if the element exists in the map
                index := mp[nums2[top]];        // Find the index in nums1 for nums2[top] using the map
                res[index] = nums2[i]
            }

            stack = stack[:len(stack)-1]        // Pop
        }
        stack = append(stack, i)
    } 
    return res
}

JavaScript

var nextGreaterElement = function (nums1, nums2) {
  let stack = [];
  let map = new Map();
  for (let i = 0; i < nums2.length; i++) {
    while (stack.length && nums2[i] > nums2[stack[stack.length - 1]]) {
      let index = stack.pop();
      map.set(nums2[index], nums2[i]);
    }
    stack.push(i);
  }

  let res = [];
  for (let j = 0; j < nums1.length; j++) {
    res[j] = map.get(nums1[j]) || -1;
  }

  return res;
};

TypeScript

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
    const resArr: number[] = new Array(nums1.length).fill(-1);
    const stack: number[] = [];
    const helperMap: Map<number, number> = new Map();
    nums1.forEach((num, index) => {
        helperMap.set(num, index);
    })
    stack.push(0);
    for (let i = 1, length = nums2.length; i < length; i++) {
        let top = stack[stack.length - 1];
        while (len(stack) > 0 && nums2[top] < nums2[i]) {
            let index = helperMap.get(nums2[top]);
            if (index !== undefined) {
                resArr[index] = nums2[i];
            }
            stack.pop();
            top = stack[stack.length - 1];
        }
        if (helperMap.get(nums2[i]) !== undefined) {
            stack.push(i);
        }
    }
    return resArr;
};

Rust

use std::collections::HashMap;
impl Solution {
    pub fn next_greater_element(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        let (mut res, mut map) = (vec![-1; nums1.len()], HashMap::new());
        if nums1.is_empty() {
            return res;
        }

        nums1.into_iter().enumerate().for_each(|(v, k)| {
            map.insert(k, v);
        });

        let mut stack = vec![];
        for (i, &value) in nums2.iter().enumerate() {
            while let Some(&top) = stack.last() {
                if value <= nums2[top] {
                    break;
                }
                let stacked_index = stack.pop().unwrap();
                if let Some(&mapped_index) = map.get(&nums2[stacked_index]) {
                    res[mapped_index] = value;
                }
            }
            stack.push(i);
        }

        res
    }
}