Got this exact question, with a small twist, at an interview less than a month ago, did a very similar approach to get linear solution and got the job.
Took me a while to understand why the time complexity is O(n). From my understanding, for each time we push a new [price, span] pair, the worst case time complexity should be O(n). However, if we consider pushing all the prices, the overall time complexity is still O(n). Because we only gonna push each pair once + pop each pair AT MOST ONCE. Great explanation!
@NeetCode Please make a videos on monotonic increasing/decreasing sequences and their patterns in questions so that we can identify problems that will need a stack.
Nice approach ♥️ I thought of something(without using pair)what if we use a count variable that is set to 1 then we push an element in stack and if the stack was empty we push 1 to our ans array. If the top of stack has larger element than incoming element then we will also push 1 since there will be no consecutives. If the top has element smaller than our incoming element than we pop until larger element is found and increment the count and push this count to ans array now for the next element if it will be larger than previous element than then can use previous count and for the rest element we can pop again and add to count and push to ans this way we don't have to use pair..
@NeetCode Even though each element will be added and removed at Max one time, but the comparisons we had to make to compute span of a particular position can be more than 1. So time complexity would be O(n*n). Detailed explanation: what we are basically doing is summing up the spans of previous peeks, provided previous peeks are smaller than the current value for which we are computing span. E.g. if data is [1,5,10,2,4,9,4,5,8,13], then to compute the span of 13, we will have to sum up spans of previous peaks smaller than 13, i.e. span(8) + span(9) + span(10).
this is my solution, is this fine? def stock_spanner(stock: List) -> List: stack = [] for i, v in enumerate(stock): if i == 0: stack.append(1) else: prev = stock[i-1] jump = 1 while v > prev and jump > 0: jump += stack[i - jump] prev = stock[i-jump] stack.append(jump) return stack
That's not a linear solution time wise. By adding the stack you worsened the space complexity from O(1) to O(n), and without changing the time complexity which is in worse case scenario O(n2). You have just to compare the number of comparison you did in the stack solution against the jump solution. No difference! A list of spans is also a stack, but instead of popping the values you just jump the index using the spans. 🤷🏻♂️ Take this expls [40,30,20,10,90,80,70,60,50,100] [90, 80, 70, 60, 50, 40, 30, 20, 10, 100]
the number of comparisons should be the same regardless of whether you pop from the stack or simply jump indexes so I guess you're correct about space complexity. However in the examples you gave , the time complexity was still O(2n) which was the worst case he mentioned. For example, in the second solution you only have to start checking the elements beforehand once you reach 100 because all the immediate previous adjacent elements for the previous values are larger which means we can immediate move on and don't have to check the span.
@@dadisuperman3472 right, I just realised haha. But I think space complexity would be O(n) regardless of whether you used a stack because you would need to create an array to store the output right?
Sorry the video cuts off before the code is complete, here's the full code: github.com/neetcode-gh/leetcode/blob/main/python/901-Online-Stock-Span.py
FYI, this link is 404 now, files got moved
WTF after spending 15 min i am stuck with half code
@@karanssh WTF after spending 15 min i am stuck with half code
class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price: int) -> int:
span = 1
while self.stack and self.stack[-1][0]
@@Neo-gy1bv class StockSpanner:
def __init__(self):
self.stack = []
# [price,span]
def next(self, price: int) -> int:
span = 1
while self.stack and self.stack[-1][0]
Got this exact question, with a small twist, at an interview less than a month ago, did a very similar approach to get linear solution and got the job.
lets goooo mario!! What job did you get?
Lucky broo
class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price: int) -> int:
span = 1
while self.stack and price >= self.stack[-1][0]:
span += self.stack[-1][1]
self.stack.pop()
self.stack.append([price, span])
return self.stack[-1][1]
Thank you neetcode
correction--
while self.stack and price > self.stack[-1][0]:
Solution is incorrect
@@calebcrf ？？
Your return statement is wrong
5 minutes in and I understand what u mean, u make such a good videos. I even sometimes watch your solutions for questions I already did.
Took me a while to understand why the time complexity is O(n). From my understanding, for each time we push a new [price, span] pair, the worst case time complexity should be O(n). However, if we consider pushing all the prices, the overall time complexity is still O(n). Because we only gonna push each pair once + pop each pair AT MOST ONCE. Great explanation!
That's not a linear time complexity.
Read my comment to understand why.
Pushing to a stack is O(1)
We go through the entire elements in 1 pass, which is why its O(n)
Thank you very much. I finally understood monotonic stack. Neetcode is a true legend
Really ingenious solution! Didn't expect this to be solved via a stack!
@NeetCode Please make a videos on monotonic increasing/decreasing sequences and their patterns in questions so that we can identify problems that will need a stack.
Nice approach ♥️
I thought of something(without using pair)what if we use a count variable that is set to 1 then we push an element in stack and if the stack was empty we push 1 to our ans array.
If the top of stack has larger element than incoming element then we will also push 1 since there will be no consecutives.
If the top has element smaller than our incoming element than we pop until larger element is found and increment the count and push this count to ans array now for the next element if it will be larger than previous element than then can use previous count and for the rest element we can pop again and add to count and push to ans this way we don't have to use pair..
The video ends for me at 15:18, cutting off before the code is completed.
Sorry about that, here's the full code: github.com/neetcode-gh/leetcode/blob/main/python/901-Online-Stock-Span.py
Amazing explanation, hats off!!
This is the best explanation, thanks
Got a similar question at my phone interview last week, hopefully I came out the solution and pass it.
i had somehwhat like this in mind but didnt really drew it out, so was kind of hazy
then i thought maybe its not feasible, so watching NC now
As usual, amazing!
Great video thanks!!
Maybe it is easier to push price/index pair to stack. Then span=currIndex-prevIndex.
Which program is he using to write on his screen like so?
I use Paint3D
11:19 What happened if the number is 65 instead ???
It would still be 1 because the problem states that we are looking for (consecutive) days since 70 is greater than 65.
You are great
If it weren’t for the design implementation of the problem, couldn’t we just use a DP array?
Actually was able to still implement it, but I guess the stack is still better space complexity.
@@Liv3fast
class Node:
def __init__(self,index,span):
self.index=index
self.span=span
def stockSpan(price, n=0) :
#Your code goes here
if len(price)==0:
return []
highest=Node(0,1)
lenn=len(price)
span_data=[0]*lenn
span_data[0]=1
i=1
while iprice[j]:
count=count+highest.span
highest.index=i
highest.span=count
span_data[i]=count
break
count=count+1
j=j-1
span_data[i]=count
i=i+1
return span_data
you can try this.....
ha! what a neat solution
Please introduce DSA and DP playlist for concept. It will help alot :)
right?
@NeetCode Even though each element will be added and removed at Max one time, but the comparisons we had to make to compute span of a particular position can be more than 1.
So time complexity would be O(n*n).
Detailed explanation: what we are basically doing is summing up the spans of previous peeks, provided previous peeks are smaller than the current value for which we are computing span.
E.g. if data is [1,5,10,2,4,9,4,5,8,13], then to compute the span of 13, we will have to sum up spans of previous peaks smaller than 13, i.e. span(8) + span(9) + span(10).
this is my solution, is this fine?
def stock_spanner(stock: List) -> List:
stack = []
for i, v in enumerate(stock):
if i == 0:
stack.append(1)
else:
prev = stock[i-1]
jump = 1
while v > prev and jump > 0:
jump += stack[i - jump]
prev = stock[i-jump]
stack.append(jump)
return stack
That's not a linear solution time wise.
By adding the stack you worsened the space complexity from O(1) to O(n), and without changing the time complexity which is in worse case scenario O(n2).
You have just to compare the number of comparison you did in the stack solution against the jump solution.
No difference!
A list of spans is also a stack, but instead of popping the values you just jump the index using the spans. 🤷🏻♂️
Take this expls
[40,30,20,10,90,80,70,60,50,100]
[90, 80, 70, 60, 50, 40, 30, 20, 10, 100]
the number of comparisons should be the same regardless of whether you pop from the stack or simply jump indexes so I guess you're correct about space complexity. However in the examples you gave , the time complexity was still O(2n) which was the worst case he mentioned. For example, in the second solution you only have to start checking the elements beforehand once you reach 100 because all the immediate previous adjacent elements for the previous values are larger which means we can immediate move on and don't have to check the span.
@@jamesmandla1192 number of comparisons is the time complexity. 😏
@@dadisuperman3472 right, I just realised haha. But I think space complexity would be O(n) regardless of whether you used a stack because you would need to create an array to store the output right?
@@jamesmandla1192 nope
Amortized time is O(1) for each call
class StockSpanner:
def __init__(self):
self.st = [] # pair: (price, span)
def next(self, price: int) -> int:
span = 1
while self.st and self.st[-1][0]
we can also return span