Online Stock Span - Leetcode 901 - Python
Vložit
- čas přidán 27. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: leetcode.com/problems/online-...
0:00 - Read the problem
1:30 - Intuition
9:40 - Walkthrough Solution
14:25 - Coding Explanation
leetcode 901
This question was identified as a meta interview question from here: github.com/xizhengszhang/Leet...
#meta #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
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]:
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.
Really ingenious solution! Didn't expect this to be solved via a stack!
Thank you very much. I finally understood monotonic stack. Neetcode is a true legend
@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.
Got a similar question at my phone interview last week, hopefully I came out the solution and pass it.
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..
As usual, amazing!
Amazing explanation, hats off!!
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)
This is the best explanation, thanks
Great video thanks!!
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
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
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
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
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.
Please introduce DSA and DP playlist for concept. It will help alot :)
Here 1st.... But what do I get, a hard qn.😐
@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).
right?
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