Next Greater Element I LeetCode
Problem Link:
https://leetcode.com/problems/next-greater-element-i/
Solution:
Approach 1 Using 2 arraylist and contains method
Stack<Integer> stack=new Stack<Integer>();
ArrayList<Integer> aa=new ArrayList<Integer>();
ArrayList<Integer> ab=new ArrayList<Integer>();
for(int i=0;i<nums2.length;i++){
ab.add(nums2[i]);
}
for(int i=nums2.length-1;i>-1;i--){
if(stack.isEmpty()){
stack.push(nums2[i]);
aa.add(-1);
}
else{
if(stack.peek()>nums2[i]){
aa.add(stack.peek());
}
else{
while(!stack.isEmpty() && stack.peek()<=nums2[i]){
stack.pop();
}
if(stack.isEmpty()){
aa.add(-1);
}
else{
aa.add(stack.peek());
}
}
stack.push(nums2[i]);
}
}
//System.out.println(aa);
Collections.reverse(aa);
//System.out.println(aa);
int arr[]=new int[nums1.length];
for(int i=0;i<nums1.length;i++){
if(ab.contains(nums1[i])){
arr[i]=aa.get(ab.indexOf(nums1[i]));
}
}
return arr;
TIME:O(N^2)[LeetCode Time: 31ms faster than 16.96% ][loops and contains method is used.
Contains method for one object => time n
In the worst case, for n objects => n^n ie n^2]
SPACE:O(N)[Stack and arraylist are used][LeetCode Memory: 39.4MB less than 61.41%]
=====================================================================
Stack<Integer> stack=new Stack<Integer>();
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
ArrayList<Integer> aa=new ArrayList<Integer>();
/*ArrayList<Integer> ab=new ArrayList<Integer>();
for(int i=0;i<nums2.length;i++){
ab.add(nums2[i]);
}*/
for(int i=nums2.length-1;i>-1;i--){
if(stack.isEmpty()){
stack.push(nums2[i]);
aa.add(-1);
}
else{
if(stack.peek()>nums2[i]){
aa.add(stack.peek());
}
else{
while(!stack.isEmpty() && stack.peek()<=nums2[i]){
stack.pop();
}
if(stack.isEmpty()){
aa.add(-1);
}
else{
aa.add(stack.peek());
}
}
stack.push(nums2[i]);
}
}
//System.out.println(aa);
Collections.reverse(aa);
//System.out.println(aa);
for(int i=0;i<nums2.length;i++){
map.put(nums2[i],aa.get(i));
}
int arr[]=new int[nums1.length];
for(int i=0;i<nums1.length;i++){
if(map.containsKey(nums1[i])){
arr[i]=map.get(nums1[i]);
}
}
return arr;
TIME:O(N)[LeetCode Time:4ms faster than 71.71%]
SPACE:O(N)[Hashmap is used][LeetCode Memory: 39.1MB less than 81.20%]
Thanks for Reading.😇
"Enlight Further To Increase Knowledge.😊"
Comments
Post a Comment