Problem

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Examples

Example 1:

Input:
nums1 = [4,1,2], nums2 = [1,3,4,2]
Output:
 [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,_4_,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [_1_,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,_2_]. There is no next greater element, so the answer is -1.

Example 2:

Input:
nums1 = [2,4], nums2 = [1,2,3,4]
Output:
 [3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

Constraints

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 104
  • All integers in nums1 and nums2 are unique.
  • All the integers of nums1 also appear in nums2.

Solution

Method 1 - Using Monotonic Decreasing Stack and Hashmap

Key Observation

Suppose we have a decreasing sequence followed by a greater number For example [5, 4, 3, 2, 1, 6] then the greater number 6 is the next greater element for all previous numbers in the sequence

We use a stack to keep a decreasing sub-sequence, whenever we see a number x greater than stack.peek() we pop all elements less than x and for all the popped ones, their next greater element is x For example [9, 8, 7, 3, 2, 1, 6] The stack will first contain [9, 8, 7, 3, 2, 1] and then we see 6 which is greater than 1 so we pop 1 2 3 whose next greater element should be 6.

Also, as elements are unique, we can use map for storing values in nums2, and update answer based on it.

Code

Java
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
	Map<Integer, Integer> map = new HashMap<>(); // map from x to next greater element of x in array 2
	Stack<Integer> stack = new Stack<>();

	for (int num: nums2) {
		while (!stack.isEmpty() && stack.peek() < num) {
			map.put(stack.pop(), num);
		}

		stack.push(num);
	}

	int[] ans = new int[nums1.length];

	for (int i = 0; i < nums1.length; i++) {
		ans[i] = map.getOrDefault(nums1[i], -1);
	}

	return ans;
}

Complexity

  • ⏰ Time complexity: O(n) where n is number of elements in nums2
  • 🧺 Space complexity: O(n) where n is number of elements in nums2