Leaders In An Array Geeks For Geeks
Problem Link:
https://practice.geeksforgeeks.org/problems/leaders-in-an-array-1587115620/1#
Solution:
class Solution{
//Function to find the leaders in the array.
static ArrayList<Integer> leaders(int arr[], int n){
Stack<Integer>stack=new Stack<Integer>();
ArrayList<Integer>aa=new ArrayList<Integer>();
for(int i=n-1;i>-1;i--){
if(stack.isEmpty()){
stack.push(arr[i]);
aa.add(-1);
}
else{
if(stack.peek()>arr[i]){
aa.add(stack.peek());
}
else{
while(!stack.isEmpty() && stack.peek()<=arr[i]){
stack.pop();
}
if(stack.size()==0){
aa.add(-1);
}
else{
aa.add(stack.peek());
}
}
stack.push(arr[i]);
}
}
Collections.reverse(aa);
ArrayList<Integer>ab=new ArrayList<Integer>();
for(int i=0;i<aa.size();i++){
if(aa.get(i)==-1){
ab.add(arr[i]);
}
}
return ab;
}
}
TIME COMPLEXITY: O(N)[GFG TIME:1.6/3.0]
SPACE COMPLEXITY: O(N)[Array Is given]
AUXILIARY SPACE: O(N)[ArrayList and Stack are used]
APPROACH USED:
Here we will find out the index of larger elements of each corresponding element using stack ad store them in ArrayList aa.
If the larger element is not present then we will store -1 in aa else we will store the value of the smaller element.
ex arr is 16 17 4 3 5 2
for this, we will start traversal from last.
Initially, the stack is empty so we will push 2 and for 2 we see there is no larger element on the right side so we will store -1.
aa={-1}
stack={2}
now for 5 no larger element is present so push into stack and add -1 in ArrayList and remove 2
aa={-1,-1}
stack={5}
now for 3 5 is larger element so we will store value 5 in aa and add 3 in stack
aa={-1,-1,5}
stack={5,3}
for 4 stack.peek() ie 3 is less so we will remove it till we reach to 5 and store new stack.peek() in aa that will be 5
aa={-1,-1,5,5}
stack={5,4}
for 17 we will remove all elements from the stack and our stack will become empty so we will add -1 in aa and later add 17 in the stack.
aa={-1,-1,5,5,-1}
stack={17}
for 16 we will see stack.peek() ie 17 is more than 16 so we will add stack.peek() in aa and 16 in stack.
aa={-1,-1,5,5,-1,17}
stack={17,16}
Now since we traverse the array from last so we need to reverse the ArrayList so formed using Collections.reverse(aa)
Now here all the elements which are -1 in aa mean they are leaders as no value greater than them exists in their right in array.
So we will store these values of elements at those particular indexes where aa.get(i)==-1.
Hence new ArrayList so formed will be returned.
TOTAL TEST CASES:410
"Thanks For Reading.😇"
"Share Further To Increase Knowledge Treasure.😊."
Comments
Post a Comment