Problem Statement:
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 <= 10000 <= nums1[i], nums2[i] <= 104- All integers in
nums1andnums2are unique.
Approach:
- Initialize an empty map to store each element’s next greater in
nums2 - Use a stack to process
nums2from right to left. - For each element:
- Pop smaller elements from the stack (they can't be NGE).
- If stack has a greater element, that’s the NGE.
- If not, NGE is -1.
- Push current element onto the stack.
- Build the answer by mapping elements from
nums1using the precomputed values from the map. - Return the result array.
Visualisation:
Time Complexity:
Time Complexity = O(n + m)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input:
nums1 = [4, 1, 2] nums2 = [1, 3, 4, 2]
State Transitions:
Initialize: stack = []
n = 4 → arr = [1, 3, 4, 2]
Push arr[3] = 2 onto stack
stack = [2]
ngeMap[2] = -1
i = 2 → arr[2] = 4
→ top = stack[stack.length-1] = 2
→ 4 > 2 → pop 2 → stack = []
→ stack empty → ngeMap[4] = -1
→ push 4 → stack = [4]
i = 1 → arr[1] = 3
→ top = 4
→ 3 < 4 → ngeMap[3] = 4
→ push 3 → stack = [4, 3]
i = 0 → arr[0] = 1
→ top = 3
→ 1 < 3 → ngeMap[1] = 3
→ push 1 → stack = [4, 3, 1]
Final ngeMap = {
2: -1,
4: -1,
3: 4,
1: 3
}
Build result from nums1 = [4, 1, 2]
→ ngeMap[4] = -1
→ ngeMap[1] = 3
→ ngeMap[2] = -1
→ ans = [-1, 3, -1]
Final Output: [-1, 3, -1]
Final State: stack = [4, 3, 1]
var nextGreaterElement = function(nums1, arr) {
let ngeMap = {};
let stack = [];
let n = arr.length;
stack.push(arr[n-1]);
ngeMap[arr[n-1]] = -1;
for(let i=n-2; i>=0; i--){
let top = stack[stack.length-1];
if(arr[i] < top){
ngeMap[arr[i]] = top;
}
else {
while(stack.length) {
if(stack[stack.length-1] < arr[i]){
stack.pop();
} else {
ngeMap[arr[i]] = stack[stack.length-1];
break;
}
}
if(stack.length === 0){
ngeMap[arr[i]] = -1;
}
}
stack.push(arr[i]);
}
let ans = [];
for(let i=0; i < nums1.length; i++){
ans.push(ngeMap[nums1[i]]);
}
return ans;
};
def nextGreaterElement(nums1, arr):
ngeMap = {}
stack = []
n = len(arr)
stack.append(arr[n - 1])
ngeMap[arr[n - 1]] = -1
for i in range(n - 2, -1, -1):
top = stack[-1]
if arr[i] < top:
ngeMap[arr[i]] = top
else:
while stack:
if stack[-1] < arr[i]:
stack.pop()
else:
ngeMap[arr[i]] = stack[-1]
break
if not stack:
ngeMap[arr[i]] = -1
stack.append(arr[i])
ans = []
for i in range(len(nums1)):
ans.append(ngeMap[nums1[i]])
return ans
import java.util.*;
public class Solution {
public int[] nextGreaterElement(int[] nums1, int[] arr) {
Map ngeMap = new HashMap<>();
Stack stack = new Stack<>();
int n = arr.length;
stack.push(arr[n - 1]);
ngeMap.put(arr[n - 1], -1);
for (int i = n - 2; i >= 0; i--) {
int top = stack.peek();
if (arr[i] < top) {
ngeMap.put(arr[i], top);
} else {
while (!stack.isEmpty()) {
if (stack.peek() < arr[i]) {
stack.pop();
} else {
ngeMap.put(arr[i], stack.peek());
break;
}
}
if (stack.isEmpty()) {
ngeMap.put(arr[i], -1);
}
}
stack.push(arr[i]);
}
int[] ans = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
ans[i] = ngeMap.get(nums1[i]);
}
return ans;
}
}
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;
vector nextGreaterElement(vector& nums1, vector& arr) {
unordered_map ngeMap;
stack s;
int n = arr.size();
s.push(arr[n - 1]);
ngeMap[arr[n - 1]] = -1;
for (int i = n - 2; i >= 0; i--) {
int top = s.top();
if (arr[i] < top) {
ngeMap[arr[i]] = top;
} else {
while (!s.empty()) {
if (s.top() < arr[i]) {
s.pop();
} else {
ngeMap[arr[i]] = s.top();
break;
}
}
if (s.empty()) {
ngeMap[arr[i]] = -1;
}
}
s.push(arr[i]);
}
vector ans;
for (int i = 0; i < nums1.size(); i++) {
ans.push_back(ngeMap[nums1[i]]);
}
return ans;
}
#include <stdio.h>
#include <stdlib.h>
#define MAX 10000
int* nextGreaterElement(int* nums1, int nums1Size, int* arr, int arrSize, int* returnSize) {
int ngeMap[MAX];
int stack[MAX];
int top = -1;
for (int i = 0; i < MAX; i++) ngeMap[i] = -2;
stack[++top] = arr[arrSize - 1];
ngeMap[arr[arrSize - 1]] = -1;
for (int i = arrSize - 2; i >= 0; i--) {
int t = stack[top];
if (arr[i] < t) {
ngeMap[arr[i]] = t;
} else {
while (top >= 0) {
if (stack[top] < arr[i]) {
top--;
} else {
ngeMap[arr[i]] = stack[top];
break;
}
}
if (top < 0) {
ngeMap[arr[i]] = -1;
}
}
stack[++top] = arr[i];
}
int* ans = (int*)malloc(nums1Size * sizeof(int));
for (int i = 0; i < nums1Size; i++) {
ans[i] = ngeMap[nums1[i]];
}
*returnSize = nums1Size;
return ans;
}
using System;
using System.Collections.Generic;
public class Solution {
public int[] NextGreaterElement(int[] nums1, int[] arr) {
Dictionary ngeMap = new Dictionary();
Stack stack = new Stack();
int n = arr.Length;
stack.Push(arr[n - 1]);
ngeMap[arr[n - 1]] = -1;
for (int i = n - 2; i >= 0; i--) {
int top = stack.Peek();
if (arr[i] < top) {
ngeMap[arr[i]] = top;
} else {
while (stack.Count > 0) {
if (stack.Peek() < arr[i]) {
stack.Pop();
} else {
ngeMap[arr[i]] = stack.Peek();
break;
}
}
if (stack.Count == 0) {
ngeMap[arr[i]] = -1;
}
}
stack.Push(arr[i]);
}
int[] ans = new int[nums1.Length];
for (int i = 0; i < nums1.Length; i++) {
ans[i] = ngeMap[nums1[i]];
}
return ans;
}
}
