Algorithm
Problem Name: 496. Next Greater Element I
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.
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. - All the integers of
nums1also appear innums2.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
unordered_map < int, int>m;
stack<int>s;
for(auto x: nums){
while(!s.empty() && s.top() < x){
m[s.top()] = x;
s.pop();
}
s.push(x);
}
for(auto& x: findNums) x = m.count(x) ? m[x] : -1;
return findNums;
}
};
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map map = new HashMap<>();
Stack < Integer> stack = new Stack<>();
for (int i = nums2.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && stack.peek() < = nums2[i]) {
stack.pop();
}
map.put(nums2[i], stack.isEmpty() ? -1 : stack.peek());
stack.push(nums2[i]);
}
int[] result = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
result[i] = map.getOrDefault(nums1[i], -1);
}
return result;
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const nextGreaterElement = function(findNums, nums) {
const map = {};
const stack = [];
for (let num of nums) {
while (stack.length && stack[stack.length - 1] < num) {
let tmp = stack.pop();
map[tmp] = num;
}
stack.push(num);
}
for (let i = 0; i < findNums.length; i++) {
findNums[i] = map[findNums[i]] == null ? -1 : map[findNums[i]];
}
return findNums;
};
console.log(nextGreaterElement([4, 1, 2], [1, 3, 4, 2]));
console.log(nextGreaterElement([2, 4], [1, 2, 3, 4]));
console.log(nextGreaterElement([1, 2, 3], [9, 8, 7, 3, 2, 1, 6]));
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def nextGreaterElement(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
out=list()
for num in nums1:
out.append(-1)
for j in range(nums2.index(num)+1,len(nums2)):
if nums2[j]>num: out[-1]=nums2[j]; break
return out
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0496_NextGreaterElementI
{
public int[] NextGreaterElement(int[] nums1, int[] nums2)
{
if (nums1.Length == 0) return nums1;
var nextElements = new Dictionary < int, int>();
var stack = new Stack<int>();
stack.Push(nums2[0]);
for (int i = 1; i < nums2.Length; i++)
{
while (stack.Count > 0 && nums2[i] > stack.Peek())
{
var num = stack.Pop();
nextElements.Add(num, nums2[i]);
}
stack.Push(nums2[i]);
}
while (stack.Count > 0)
{
var num = stack.Pop();
nextElements.Add(num, -1);
}
for (int i = 0; i < nums1.Length; i++)
nums1[i] = nextElements[nums1[i]];
return nums1;
}
}
}
Input
Output