Table of Contents
Problem Statement
In this problem, we are given two lists in which first list is subset of second list. For each element of first list, we have to find out next greater element in the second list.
Example
nums1 = [4,1,2], nums2 = [1,3,4,2]
[-1,3,-1]
Explanation:
for first element of list1 i.e. for 4 there is no next greater element in list2, thus its answer is -1.
for second element of list1 i.e. for 1 there is 3 greater than 1 in list 2, thus its answer is 3.
for third element of list1 i.e. for 2 there is no next greater element in list2, thus its answer is -1.
nums1 = [2,4], nums2 = [1,2,3,4]
[3,-1]
Approach 1 (Brute Force)
In this approach, we simply find next greater element for each element of list1 by doing linear traversal in list2 using a nested for loop.
Each element of list1 is first searched in list2, then afterwards its next greater element is searched. We are doing this by using a flag variable. For each element of list1, it is first set to false. When we have found the element in list2, it is set to true. After that, when we will find the next greater, we will set it to false again. By doing so, we will get to know that there is any next greater element in list2 for that variable or there isn’t any.
- If the flag variable is true, it means we could not find any next greater value for that element.
- If the flag variable is false, it means that we have found one next greater value for that element.
So, at end of each inner loop, according to flag value we will insert -1 as our answer.
Implementation for Next Greater Element I Leetcode Solution
C++ Program
#include <iostream>
#include <vector>
using namespace std;
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
vector<int> ans;
for(int i=0;i<nums1.size();i++){
bool flag=false;
for(int j=0;j<nums2.size();j++){
if(nums1[i]==nums2[j])flag=true;
if(flag && nums1[i]<nums2[j]){
ans.push_back(nums2[j]);flag=false;break;
}
}
if(flag)ans.push_back(-1);
}
return ans;
}
int main()
{
vector<int> nums1{ 4,1,2 };
vector<int> nums2{ 1,3,4,2 };
vector<int>ans=nextGreaterElement(nums1,nums2);
for(int i=0;i<ans.size();i++){
cout<<ans[i]<<" ";
}
}-1 3 -1
Java Program
import java.util.*;
import java.lang.*;
class Solution
{
public static void main(String args[])
{
int[]nums1={4,1,2};
int[]nums2={1,3,4,2};
int[]ans=nextGreaterElement(nums1,nums2);
for(int i:ans){
System.out.print(i+" ");
}
}
public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[]ans=new int[nums1.length];
for(int i=0;i<nums1.length;i++){
boolean flag=false;
for(int j=0;j<nums2.length;j++){
if(nums1[i]==nums2[j])flag=true;
if(flag && nums1[i]<nums2[j]){
ans[i]=nums2[j];flag=false;break;
}
}
if(flag)ans[i]=-1;
}
return ans;
}
}-1 3 -1
Complexity Analysis for Next Greater Element I Leetcode Solution
Time Complexity
O(m*n): For each element of nums1 we are traversing nums2 linearly from left to right. Thus, time complexity is O(m*n) where m and n are length of lists.
Space Complexity
O(1): No extra space used (spaced used for ans array isn’t considered because that is necessary).
Approach 2 (Using Stack)
This approach comprises of two parts.
Firstly, we are using a stack to get the next greater element of each element of list2 in linear time. The next greater element of each element is stored in a map.
Secondly, we will store answer for each element of list1 in our answer array by using the map.
So, we will traverse the list2 and repeatedly pop all elements from the top of stack which are smaller than current number and simultaneously, at each pop we will record the current element as the nearest greater answer of each popped element. For this mapping, we will simply use a map.
Now, we have a map which is just a mapping of elements with their respective next greater elements.
Finally, we will traverse the list1 and store their respective values from map in our answer list.
Implementation for Next Greater Element I Leetcode Solution
C++ Program
#include <iostream>
#include <vector>
#include <stack>
#include <map>
using namespace std;
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack<int>stack;
map<int,int>map;
vector<int>ans;
for(int i=0;i<nums2.size();i++){
while(!stack.empty()){
if(stack.top()<nums2[i]){
map.insert(pair<int,int>(stack.top(),nums2[i]));
stack.pop();
}else break;
}
stack.push(nums2[i]);
}
for(int i=0;i<nums1.size();i++){
int val = map[nums1[i]];
if(val==0)ans.push_back(-1);
else ans.push_back(val);
}
return ans;
}
int main()
{
vector<int> nums1{ 4,1,2 };
vector<int> nums2{ 1,3,4,2 };
vector<int>ans=nextGreaterElement(nums1,nums2);
for(int i=0;i<ans.size();i++){
cout<<ans[i]<<" ";
}
}-1 3 -1
Java Program
import java.util.*;
import java.lang.*;
class Solution
{
public static void main(String args[])
{
int[]nums1={4,1,2};
int[]nums2={1,3,4,2};
int[]ans=nextGreaterElement(nums1,nums2);
for(int i:ans){
System.out.print(i+" ");
}
}
public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
Stack<Integer>stack=new Stack<Integer>();
Map<Integer,Integer>map=new HashMap<Integer,Integer>();
int[]ans=new int[nums1.length];
for(int i:nums2){
while(!stack.isEmpty()){
if(stack.peek()<i){
map.put(stack.peek(),i);
stack.pop();
}else break;
}
stack.push(i);
}
for(int i=0;i<nums1.length;i++){
if(map.containsKey(nums1[i]))
ans[i]=map.get(nums1[i]);
else ans[i]=-1;
}
return ans;
}
}-1 3 -1
Complexity Analysis for Next Greater Element I Leetcode Solution
Time Complexity
O(m+n): Firstly, we are traversing list2 to find next greater element for all elements of list2. Then, we are traversing list1 to append the answers. So, time complexity is sum of length of both lists.
Space Complexity
O(n): We are using a map to find answer to any key in O(1) time, thus the space complexity is O(n).