Back to DSA
Next Greater Element I
easyYou are given two arrays of distinct integers, subset and source, where every element of subset also appears in source. For each element in subset, locate the first value to its right within source that is strictly larger. Collect these results into an output array, using -1 wherever no such larger value exists.
Examples
Example 1:
Input:
nums1 = [2,4,1], nums2 = [1,2,3,4,5]Output:
[3,5,2] Example 2:
Input:
nums1 = [3,1], nums2 = [3,1,2]Output:
[-1,2]Hints
import java.util.*;
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<>();
Deque<Integer> stack = new ArrayDeque<>();
for (int num : nums2) {
while (!stack.isEmpty() && stack.peek() < num) map.put(stack.pop(), num);
stack.push(num);
}
int[] result = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) result[i] = map.getOrDefault(nums1[i], -1);
return result;
}
}Time complexity
O(n + m)Space complexity
O(n)