Stock Span Problem Geeks For Geeks
class StoreStack{
int val;
int data;
}
class Solution
{
//Function to calculate the span of stock’s price for all n days.
public static int[] calculateSpan(int arr[], int n)
{
ArrayList<Integer> aa=new ArrayList<Integer>();
StoreStack obj[]=new StoreStack[n];
Stack<StoreStack> stack=new Stack<StoreStack>();
for(int i=0;i<n;i++){
obj[i]=new StoreStack();
obj[i].val=arr[i];
obj[i].data=i;
}
/*for(int i=0;i<n;i++){
System.out.println(obj[i].val+" "+obj[i].data);
}*/
for(int i=0;i<n;i++){
if(stack.isEmpty()){
aa.add(-1);
}
else{
if(stack.peek().val>arr[i]){
aa.add(stack.peek().data);
}
else{
while(!stack.isEmpty() && stack.peek().val<=arr[i]){
stack.pop();
}
if(stack.isEmpty()){
aa.add(-1);
}
else{
aa.add(stack.peek().data);
}
}
}
stack.push(obj[i]);
}
//System.out.println(aa+" ");
//Finding difference with index so as to get actual count
for(int i=0;i<aa.size();i++){
aa.set(i,i-aa.get(i));
}
//System.out.println(aa+" ");
for(int i=0;i<n;i++){
arr[i]=aa.get(i);
}
return arr;
}
}
Approach:
Here we need to return the count array:
count = no of consecutive smaller elements in left + number itself
for smaller elements in left:
we will find out the nearest greater element to left. It's so because while searching for the greater element on the left we will navigate through all smaller elements that occur in between. So we will break as we find the first left greater element.
If we observe clearly then we need to return count which will be the number of elements in between selected element and its nearest greater element, So if I know the index of both elements then directly by their difference I can get the value of count.
Now our motive is to find (current_index- index_of_nearest_greater_left) for all elements of input array.
For that, we will apply the logic of finding the nearest greater element to left but with the modification that earlier we were storing element but now we will store the index of the element.
For this reason, only a new class named StoreStack has been created which will store val ie element and data ie index of the element in the array.
[Can we can store elements in one ArrayList and later its index in another ArrayList using indexOf() function. Answer ..... NO. Because indexOf() will return the first occurrence index of element, so for any element with multiple occurrences it will fail.
ex 60 100 60 50 70 80 60 75
will have the first ArrayList of greater elements ie -1 -1 100 60 100 100 80 80
second ArrayList of index ie -1 -1 1 0 1 1 5 5
however, answer according to indexes should be -1 -1 1 2 1 1 5 5
so that's why we are using a separate class and its object = {element, index of element} will be stored.]
In the main class, the main stack will be there with the same code of nearest greater to left with modifications that
1. Comparision of arr[i] now will be with the stack. peek().val
2. storage of stack. peek().data will be there in ArrayList which will be returned later.
Later each element of ArrayList so formed will be differenced from the index. [So to find the actual count between the current element and its obtained nearest greater element in left using indexes.]
Hence result obtained is ArrayList which will be returned.
TIME:O(N) [No nested loops are used][GFG Time: 8.3/11]
SPACE:O(N)[ArrayList and Stack are used]
Thanks for Reading.😇
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment