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.
@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.
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!
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?
