ooooooooooo bhaiiiiiiiiii never ever thought that this question can be solved in this way too what an explaination bhaiiii subscribed you after watching the optimisation part bro
Great solution. Just one suggestion, It would be better if you can prove that there will be O(n) comparisons in total rather than giving a bunch of examples for it. Edit - Case where last solution doesn't work linearly - [x,1, x,1, x,1 ... 2,3,4,5...,x] For each [x,1] that appears on the left, there will be x iterations. Say x = n/2 . Then the number of comparisons in that case array will be n/4 * n/2.
Sir, it's truly ingenious, thanks for proving this beautiful solution. But while I don't claim to have any expertise in this area, I would like to express my understanding that, theoretically, the space complexity appears to be O(n) due to the proportional dependence on the input size. It's worth noting that the solution refers to those values in the array for calculations, effectively storing intermediate values within the array. Also from my limited knowledge, it seems that, for larger inputs, the solution might not be as memory-efficient as alternative approaches, such as using an additional stack and storing the result in the input array. If you could address these concerns, that would be greatly appreciated. Looking forward to your insights!
@moupiya9286 But, bro here we are returning the vector as an answer, while computing the space complexity, we keep in mind that what is the extra space used for computing the answer or the required output, here the output required itself, is an array, this means this is what we are computing, and to compute this we need this, and TO NEED THIS, what extra space is used ?? Nothing, (but just a handful of variables which is O(1) in space complexity ), so we will not count this in our complexity, that is why the space complexity here is O(1), I hope I can make it understandable to you.
@@SidharthjainSingla Thank you for the detailed explanation, and I now understand the reasoning behind the O(1) space complexity. It's certainly a beautiful solution. My curiosity extends to a broader comparison-when there are no constraints on modifying the input array, do you think the O(1) approach is generally more advantageous than an O(k) solution using a stack? Since the constraints didn't limit modifications to the input array, I'm interested in understanding the practicality of these different approaches. I must admit that I only watched the O(1) part of the video, not the entire video, so I'm unsure whether the input array was modified. However, my initial thought is that many people might have opted for modifying the input array since there were no constraints about that. Looking forward to hearing your insights and thoughts. Thank you once again.
@@moupiya9286 In the first approach, we used the *Monotonic Stack* (when *Stack* is used with some constraints like push the number only when top of the stack is smaller or greater or same with pop i.e., when the current element is big or small than top of the stack ,i.e., when we are constraining the stack to just store numbers in a *increasing* or *equal and increasing* or *decreasing* or *equal and decreasing* , This property or fashion of using stack is known as monotonic stack) for storing the next greater element for the current element and doing this for all the elements present in the array. In this approach ofcourse the time complexity is O(n) where n is the number of elements in the given array. Why the time complexity is O(n) because in the worst case it might be possible that the given array is sorted in non decreasing order then we need to insert all the elements in the array. In the second approach, we didn’t alter the data present in the given array, but the answer array we created which will not be comprised in the space complexity because this we have to return it to the function and the thing we return to the function in *most cases* is not accountable in space complexity *unless* it is mentioned that you have to return the same given array with some altering done on it and if then you used a another array then it will be counted in the space complexity because it was mentioned that you have to return the same given array with some alterations done on it. In the second approach, we used the calculated values of the answer array to calculate the next greater element for the current element , you can say it is some sort of a dp-memoization which we do in dp not exactly this we do , but yeah sort of, dp actually means to solve the sub-problems and to calculate another sub problem we used the results of the calculated sub-problems. This is the basic definition of dynamic programming. That is why the space complexity in second approach is O(1). Thanks buddy…:)
if we have (10^4) ,1,2,3,4,5,6,.............(10^4)+1 in this case firstly from back we tend to iterate and calculate the warmer day till index 1 it will be (n-1) and at index 0 it will again iterate i.e: n-1 +(1+1+1+1+1+1+1+....n) which will be 2*n is it?
wow, i guess people are rude nowadays, trust me bro, there is no silly doubts, and also know that only incompetent people will comment such type of things and will judge you, do not get demotivated, keep going
Actually he has excluded the space required for the stack to find next greater value but returning vector is required for the question as question is asking for next greater value at each index
![โฮ่ง! (SUGOI) - LYKN [ OFFICIAL MV ]](http://i.ytimg.com/vi/nFp4zjAARFs/mqdefault.jpg)
That space optimization part.....just mindblowing !!!
Thank you for the video !!
Never thought that wow!Real time use of memoization
You're so underrated bro, I just loved your explanation. Thanks for your O(1) Space Optimization :)
Maza a gaya yr. Question karo to aise, analyse karke. PhD in DS Algo.
ooooooooooo bhaiiiiiiiiii never ever thought that this question can be solved in this way too
what an explaination bhaiiii
subscribed you after watching the optimisation part bro
Great solution. Just one suggestion, It would be better if you can prove that there will be O(n) comparisons in total rather than giving a bunch of examples for it.
Edit - Case where last solution doesn't work linearly -
[x,1, x,1, x,1 ... 2,3,4,5...,x]
For each [x,1] that appears on the left, there will be x iterations. Say x = n/2 . Then the number of comparisons in that case array will be n/4 * n/2.
So nicely explained 👍👍
Sir, it's truly ingenious, thanks for proving this beautiful solution. But while I don't claim to have any expertise in this area, I would like to express my understanding that, theoretically, the space complexity appears to be O(n) due to the proportional dependence on the input size. It's worth noting that the solution refers to those values in the array for calculations, effectively storing intermediate values within the array. Also from my limited knowledge, it seems that, for larger inputs, the solution might not be as memory-efficient as alternative approaches, such as using an additional stack and storing the result in the input array. If you could address these concerns, that would be greatly appreciated. Looking forward to your insights!
@moupiya9286 But, bro here we are returning the vector as an answer, while computing the space complexity, we keep in mind that what is the extra space used for computing the answer or the required output, here the output required itself, is an array, this means this is what we are computing, and to compute this we need this, and TO NEED THIS, what extra space is used ?? Nothing, (but just a handful of variables which is O(1) in space complexity ), so we will not count this in our complexity, that is why the space complexity here is O(1), I hope I can make it understandable to you.
@@SidharthjainSingla Thank you for the detailed explanation, and I now understand the reasoning behind the O(1) space complexity. It's certainly a beautiful solution. My curiosity extends to a broader comparison-when there are no constraints on modifying the input array, do you think the O(1) approach is generally more advantageous than an O(k) solution using a stack? Since the constraints didn't limit modifications to the input array, I'm interested in understanding the practicality of these different approaches.
I must admit that I only watched the O(1) part of the video, not the entire video, so I'm unsure whether the input array was modified. However, my initial thought is that many people might have opted for modifying the input array since there were no constraints about that. Looking forward to hearing your insights and thoughts. Thank you once again.
@@moupiya9286 In the first approach, we used the *Monotonic Stack*
(when *Stack* is used with some constraints like push the number only when top of the stack is smaller or greater or same with pop i.e., when the current element is big or small than top of the stack ,i.e., when we are constraining the stack to just store numbers in a *increasing* or *equal and increasing* or *decreasing* or *equal and decreasing* , This property or fashion of using stack is known as monotonic stack) for storing the next greater element for the current element and doing this for all the elements present in the array.
In this approach ofcourse the time complexity is O(n) where n is the number of elements in the given array.
Why the time complexity is O(n) because in the worst case it might be possible that the given array is sorted in non decreasing order then we need to insert all the elements in the array.
In the second approach, we didn’t alter the data present in the given array, but the answer array we created which will not be comprised in the space complexity because this we have to return it to the function and the thing we return to the function in *most cases* is not accountable in space complexity *unless* it is mentioned that you have to return the same given array with some altering done on it and if then you used a another array then it will be counted in the space complexity because it was mentioned that you have to return the same given array with some alterations done on it.
In the second approach,
we used the calculated values of the answer array to calculate the next greater element for the current element ,
you can say it is some sort of a dp-memoization which we do in dp not exactly this we do , but yeah sort of, dp actually means to solve the sub-problems and to calculate another sub problem we used the results of the calculated sub-problems. This is the basic definition of dynamic programming.
That is why the space complexity in second approach is O(1). Thanks buddy…:)
bhai ko roz video banate time call aate hai 🤪
great keep going 💪💪💪💪💪💪
Bhaiya dsa playlist start kijiye phir se usme aise question kariye jisme sb topic ke pattern cover ho jaye
hey I'm getting tle for this optimized approach ? is it because I used python ? But the stack solution worked🤔
because its not O(n)
if we have (10^4) ,1,2,3,4,5,6,.............(10^4)+1 in this case firstly from back we tend to iterate and calculate the warmer day till index 1 it will be (n-1) and at index 0 it will again iterate i.e: n-1 +(1+1+1+1+1+1+1+....n) which will be 2*n is it?
but this is just one worst case and for sure this is O(2* n) and we know that O(k*n) is the same as O(n).
Amazing>>>
how can you say that the given question is medium hard it most easy problem ever encountered
Wowwww
But for this test case 8 1 2 3 4 5 6 7 9 it will be n2 right
its 2*n as except 8 everyone is just being compared once
How is this O(1) space when the vector ans that your are returning is of size n?
bruhh
Jaa tu tcs ke liye bana h 😂😂😂
You are confusing between time complexity and space complexity it seems. Pls read about them indepth & comeback.
wow, i guess people are rude nowadays, trust me bro, there is no silly doubts, and also know that only incompetent people will comment such type of things and will judge you, do not get demotivated, keep going
Actually he has excluded the space required for the stack to find next greater value but returning vector is required for the question as question is asking for next greater value at each index
Abea Late q hua !
🫡