Great explanation. The difficult part was understanding the question. The runtime went from 45ms to 26ms (for java) when I initialized the index to start from 1 and simply returned the index instead of index + 1 and incremented the index after pushing to the stack. Not sure why though.
@@techdose4u Yeah I think so too. Here is the full code: class StockSpanner { Stack stack = new Stack(); int index; public StockSpanner() { index = 1; } public int next(int price) { int span = 0; while(!stack.isEmpty() && stack.peek().price
Hi, you guys are doing a great job, and I completely support you and wish you all the best. Can you please have a look at leetcode 1130 Minimum Cost Tree From Leaf Values, and if possible, make a video on it.
Is the benefit of stock span is finding whether the stock is increasing or decreasing with time span, by analysing the stock for a long time period and finding the ranges of increasing or decreasing max or min values for either buying or selling time
both of the time and space is O(N) right, imo each element only push and pop from the (monotonic) stack once. please correct me if I am wrong with the analysis, thanks a lot!
@TECHDOSE I just simplified your code to this: class StockSpanner { stack s; // int index; public: StockSpanner() { ios_base::sync_with_stdio(false); cin.tie(NULL); // index = -1; } int next(int price) { if(s.empty() or price < s.top().first){ s.push({price, 1}); return 1; }else{ int i = 1; while(!s.empty() and s.top().first
Didn't even open your video and solved it since you gave it out with just the title , greater element..... 😂😂😂 Now I feel that even by looking at your title and cover picture you gave out more than enough information that I need to solve the problem hahahaha
Java Solution class StockSpanner { Stack stock=new Stack(); Stack day=new Stack(); public StockSpanner() { } public int next(int price) { int count=1; while(!stock.isEmpty() && stock.peek()
It can be solved using LinkedList with same space and time complexity. Just store the price, span at that particular day and address of previous greater element.
Yea.....actaually you will only be implementing stack using linked list. You can even use array. But the meaning is same. We are just implementing stack.
@@techdose4u I won't say this is STACK using LL. Have a look in my c# code. public class NodeInfo { public NodeInfo nextBiggerNode; public int price; public int count; public NodeInfo(NodeInfo node, int p, int c) { nextBiggerNode = node; price = p; count = c; } } public class StockSpanner { LinkedList stock; public StockSpanner() { stock = new LinkedList(); } public int Next(int price) { int count = 1; NodeInfo temp = null; if (stock.First != null) temp = stock.First.Value; //head while(temp != null && temp.price
well sir, you used index, but i used span itself(storing it and then using it).....in the following code #include #include using namespace std; stack> S; int main(){ int n, val; cin>>n; for(int i=0; i< n; i++){ cin>> val; int span= 1; while(!S.empty() && S.top().first val) S.push({val, span}); cout
It has just been 1 year....started from scratch. Adding 2 numbers using recursion 😅. I took 1 year break and again restarted 8 months back and now I won't stop :D
English is better for everybody so don't want other languages sir I love this channel because of precise content, clear explanation, and easy to understand.
I mess up this question. Without even reading the statement I looked to the first example and made an idea: We need an online algorithm and count inversions, Hence used Fenwick Tree. After this I got 4 WA. Hey if you got some time would you please cover this problem leetcode.com/problems/implement-rand10-using-rand7/ .
These challenge problems are simple only. Expectations plays with mind a lot 😅 May be you are practicing and using it so much that you tend to apply them at places it is not required.
still you counting inversions using fenwick tree , for current element you will find all the smaller at the left, but you cannot promise that they will be consecutive ...so i think it will fail there
@@techdose4u I got this problem from "Daily Coding Problem" that question was a little bit different in that question you have to implement rand7() using rand5(). The only thing where I'm confused is, for uniform sampling why we need to multiply with the same random number generator. i.e. for rand10() you have to do 10*rand10(), for rand5() you have to do 5*rand5().
@@manthankhorwal1477 Yup after getting the Wrong Answer I realized my mistake that it can't be solved with counting inversion method , and then I took Stack approach. "still you counting inversions using Fenwick tree" --> I just know counting inversion through "segment tree", "Fenwick Tree", "trie", "merging" and with policy-based data structure (in C++ only). Out of these only Segment tree & Fenwick Tree are online algorithms. If you have a better approach then please do share.
Nice solution. I thought of BST actually.
thank you!
🤔
Great explanation. The difficult part was understanding the question. The runtime went from 45ms to 26ms (for java) when I initialized the index to start from 1 and simply returned the index instead of index + 1 and incremented the index after pushing to the stack. Not sure why though.
It should be same time 🤔
@@techdose4u Yeah I think so too. Here is the full code:
class StockSpanner {
Stack stack = new Stack();
int index;
public StockSpanner() {
index = 1;
}
public int next(int price) {
int span = 0;
while(!stack.isEmpty() && stack.peek().price
nice, thank you for sharing. very clear
Great explanation, thank you!
Welcome :)
great explaination
Hi, you guys are doing a great job, and I completely support you and wish you all the best. Can you please have a look at leetcode 1130 Minimum Cost Tree From Leaf Values, and if possible, make a video on it.
Is the benefit of stock span is finding whether the stock is increasing or decreasing with time span, by analysing the stock for a long time period and
finding the ranges of increasing or decreasing max or min values for either buying or selling time
both of the time and space is O(N) right, imo each element only push and pop from the (monotonic) stack once.
please correct me if I am wrong with the analysis, thanks a lot!
Correct :)
@TECHDOSE
I just simplified your code to this:
class StockSpanner {
stack s;
// int index;
public:
StockSpanner() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// index = -1;
}
int next(int price) {
if(s.empty() or price < s.top().first){
s.push({price, 1});
return 1;
}else{
int i = 1;
while(!s.empty() and s.top().first
Thank you sir for being such a wonderful teacher!
Welcome 😊
Didn't even open your video and solved it since you gave it out with just the title , greater element..... 😂😂😂 Now I feel that even by looking at your title and cover picture you gave out more than enough information that I need to solve the problem hahahaha
Hahaha 😂 Great ❤️
👌👌👌
😁
Thank you
Java Solution
class StockSpanner {
Stack stock=new Stack();
Stack day=new Stack();
public StockSpanner() {
}
public int next(int price) {
int count=1;
while(!stock.isEmpty() && stock.peek()
Thanks for sharing
It can be solved using LinkedList with same space and time complexity. Just store the price, span at that particular day and address of previous greater element.
Yea.....actaually you will only be implementing stack using linked list. You can even use array. But the meaning is same. We are just implementing stack.
@@techdose4u not particularly stack. I would never pop in my implementation. But yes, it will work like stack.
That's the point 😅 Implementation of stack using LL
@@techdose4u I won't say this is STACK using LL. Have a look in my c# code.
public class NodeInfo {
public NodeInfo nextBiggerNode;
public int price;
public int count;
public NodeInfo(NodeInfo node, int p, int c) {
nextBiggerNode = node;
price = p;
count = c;
}
}
public class StockSpanner {
LinkedList stock;
public StockSpanner() {
stock = new LinkedList();
}
public int Next(int price) {
int count = 1;
NodeInfo temp = null;
if (stock.First != null)
temp = stock.First.Value; //head
while(temp != null && temp.price
thank you. helped me
Welcome
What is the total time taken for all test cases?
Don't remeber bro.....Maybe around 400 ms (not sure).
You have good knowldge, can you tell your study background?
I don't have CS background. Currently I am learning with you guys and trying each day to improve myself :)
@@techdose4u If this is learning, then we are nowhere...
@@techdose4u if you don't have computer background then can you tell to all the roadmap for learning data structures and algorithms..
@@techdose4u plz tell or suggest any resources where I can learn deeply and in efficient manner
thanks
Welcome :)
Sir how will you do every problem soo quickly??..it's took more time for me to read and understand the problem😥
I have solved similar problems so it was easy. You need to keep practicing :)
u are arranging stack in increasing order or decreasing order its is difficult for me to understand though ur explanation is good.
In descending order. I explained why we will take decresing order and not increasing order.
well sir, you used index, but i used span itself(storing it and then using it).....in the following code
#include
#include
using namespace std;
stack> S;
int main(){
int n, val;
cin>>n;
for(int i=0; i< n; i++){
cin>> val;
int span= 1;
while(!S.empty() && S.top().first val)
S.push({val, span});
cout
Please make string questions playlist
Many string questions are present. I have not organized the problems. I will do it once I get time.
@@techdose4u okkk thanks big bro
Simple stack application
Correct :D
in which company u work?
srib
And when you started coding?
It has just been 1 year....started from scratch. Adding 2 numbers using recursion 😅. I took 1 year break and again restarted 8 months back and now I won't stop :D
@@techdose4u your videos are really good. maybe one day we'll meet in goole headquarters😂😂
Just kidding
stackindices;
StockSpanner() {
}
int next(int price) {
if(indices.empty())
{
indices.push({price,1});
return 1;}
auto x=indices.top();
if(x.first>price)
{ indices.push({price,1});
return 1;}
else {
int count=1;
while(indices.empty()==false && price>=x.first)
{
count+=x.second;indices.pop();
x=indices.top();
}
indices.push({price,count});
return count;
}
}
};
//This says "reference binding to misaligned address !" Can anyone please look into it ?
Thank you
Superb, superb explanation. There should be some hindi/urdu
😅
@@techdose4u i am serious
English is better for everybody so don't want other languages sir
I love this channel because of precise content, clear explanation, and easy to understand.
English language is common for programmers.
I mess up this question. Without even reading the statement I looked to the first example and made an idea: We need an online algorithm and count inversions, Hence used Fenwick Tree. After this I got 4 WA.
Hey if you got some time would you please cover this problem leetcode.com/problems/implement-rand10-using-rand7/ .
These challenge problems are simple only. Expectations plays with mind a lot 😅 May be you are practicing and using it so much that you tend to apply them at places it is not required.
still you counting inversions using fenwick tree , for current element you will find all the smaller at the left, but you cannot promise that they will be consecutive ...so i think it will fail there
Tried your question. Used every trick except sampling 😅 Since it was not creating any multiple of 10 so had to sample. Nice question.
@@techdose4u I got this problem from "Daily Coding Problem" that question was a little bit different in that question you have to implement rand7() using rand5(). The only thing where I'm confused is, for uniform sampling why we need to multiply with the same random number generator. i.e. for rand10() you have to do 10*rand10(), for rand5() you have to do 5*rand5().
@@manthankhorwal1477 Yup after getting the Wrong Answer I realized my mistake that it can't be solved with counting inversion method , and then I took Stack approach. "still you counting inversions using Fenwick tree" --> I just know counting inversion through "segment tree", "Fenwick Tree", "trie", "merging" and with policy-based data structure (in C++ only). Out of these only Segment tree & Fenwick Tree are online algorithms. If you have a better approach then please do share.
I guessed that was stack, but I didn't know how to implement it :(
Keep practicing and solving. You will solve these with ease :)
The video is very helpful but your voice is irritating af.
😅