Next Greater Element Geeks For Geeks And InterviewBit
Approach 1: Using ArrayList
ArrayList<Long> aa=new ArrayList<Long>();
Stack<Long>stack=new Stack<Long>();
for(int i=n-1;i>-1;i--){
if(stack.isEmpty()==true){
aa.add(Long.valueOf(-1));
}
else{
if(stack.peek()>arr[i]){
aa.add(stack.peek());
}
else{
while(!stack.isEmpty() && stack.peek()<=arr[i]){
stack.pop();
}
if(stack.isEmpty()==true){
aa.add(Long.valueOf(-1));
}
else{
aa.add(stack.peek());
}
}
}
stack.push(arr[i]);
}
Collections.reverse(aa);
long arr1[]=new long[aa.size()];
for(int i=0;i<aa.size();i++){
arr1[i]=aa.get(i);
}
return arr1;
TIME:O(N)[GFG Time:2.9/4.6][Not Exactly Sure, Near About This Range]
SPACE:O(N)[Array And ArrayList Both Are Used]
*********************************************************************************
Approach 2: Using Array Directly
ArrayList<Long> aa=new ArrayList<Long>();
Stack<Long>stack=new Stack<Long>();
long arr1[]=new long[arr.length];
for(int i=n-1;i>-1;i--){
if(stack.isEmpty()==true){
arr1[i]=(Long.valueOf(-1));
}
else{
if(stack.peek()>arr[i]){
arr1[i]=(stack.peek());
}
else{
while(!stack.isEmpty() && stack.peek()<=arr[i]){
stack.pop();
}
if(stack.isEmpty()==true){
arr1[i]=(Long.valueOf(-1));
}
else{
arr1[i]=(stack.peek());
}
}
}
stack.push(arr[i]);
}
for(int i=0;i<n/2;i++){
long temp=arr[i];
arr[i]=arr[n-i-1];
arr[n-i-1]=temp;
}
return arr1;
TIME:O(N)[GFG Time:2.9/4.6][Sure]
SPACE:O(N)[Array Is Used Only]
***********************************************************************************
InterviewBit:
Thanks For Reading.😇
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment