Next Greater Element | Two Variants | Leetcode

[@takeUforward]

While writing code, it should have been.. 2n-1 to 0 😅 You can also do by front passing, but that will take more time, as you have to store index, and then retract them.. leetcode.com/problems/next-greater-element-ii/discuss/98270/JavaC%2B%2BPython-Loop-Twice

[@kakoli960]

I am in comment section just to check that if I am only not understanding or the code had mistakes.. thanks for this

[@hh8xking30]

@@kakoli960 and we too have to reverse the output array as we are doing operations from last. and we have to show output from first.

[@akshayzade9761]

Thanks @Striver Correction 1 - for(int i=((2*n)-1); i>=0 ; i--) Correction 2 - while( (!stack.isEmpty()) && (stack.peek()

[@subhampandey7374]

😄

[@SwapnilSarkar]

This mistake wasted so much of my time

[@nikhilpatro5905]

Dude, you have such good teaching skills! I have been a TA at coding ninjas so I know how hard it is to explain an algorithm. Please never stop teaching :)

[@akshitkumar9402]

> I have been a TA at coding ninjas literally nobody asked

[@mudrad1930]

so a coding ninja TA also using free resources 😂😂

[@vishal40007]

@@mudrad1930 There always something new to learn

[@allhdmoviescene1294]

no more learning from coding ninja

[@kritidiptoghosh4272]

Really good explaination. Just wanted to add something for those ,who are still not 100% sure about why the stack technique is working. Just Think of the numbers as poles casting shadow(To their right,bcoz we see from left ). Lets say the next larger pole for a particular index is L. Because we are looking from the left side, when we see L we will not be able to see the poles on its right which are smaller than L because they are overshadowed. But the poles on L's right which are larger than L can still be seen because they are taller. (Thats why they are in stack). The stack at any position is literally what we would see standing there looking at right.

[@abinvarkey2331]

thanks for that tip :)

[@tear7934]

woah really nice intuition!! thanks

[@amogu_07]

thanks so much !! that's an awesome intuition !!

[@thor1626]

the loop cond should be for (int i = (len * 2) - 1; i >= 0; i--)

[@simranagarwal4813]

yes, u r right.

[@nayanbhuyan8156]

To make things even more simpler, if(i < n) condition is not required, instead write i % 2 in other steps, like: vector nextGreaterElements(vector& nums) { int n = nums.size(); vector res(n); stack st; for(int i = 2 * n - 1; i >= 0; i--) { while(!st.empty() && nums[i % n] >= st.top()) st.pop(); if(st.empty()) res[i% n] = -1; else res[i % n] = st.top(); st.push(nums[i % n]); } return res; }

[@babai2196]

thanks bro

[@PIYUSH-lz1zq]

for first variant why we running for 2*n-1 ... it should be done only for circular onces !!

[@pranavsharma7479]

@@PIYUSH-lz1zq no for first run for n-1 to 0 only

[@amanbhadani8840]

This code allows same values to be reassigned,thats not logical and not prefered.

[@adwiteek5936]

Avoid using maps in these circular array types of questions as you might get wrong answer by storing different value for same key in a map..... you can directly return the vector on leetcode when you will be iterating from i

[@harshalgarg1149]

Another approach that can be used is that first we put all the elements in stack while traversing backwards from the end and then use the same code that was used for the first variation. vector nextGreaterElements(vector& v) { vector vans; int n = v.size(); stack st; for(int i=n-1;i>=0;i--) st.push(v[i]); for(int i=n-1;i>=0;i--) { while(!st.empty() and st.top()

[@akshaykenjale2642]

In Next Greater Elements problem I guess instead of i

[@PIYUSH-lz1zq]

for first variant why we running for 2*n-1 ... it should be done only for circular onces !!

[@amanbhadani8840]

@@PIYUSH-lz1zq Not required for first variant bro.

[@maccall0108]

brother we can also store array index from n-2 to 0 in stack and then apply the similer logic as we have applied in Ques ->next-greater element -I and before returning our vector we just need to reverse it. vectorv; stacks; int siz=nums.size(); for(int i=siz-2;i>=0;i--) { s.push(nums[i]); //store from n-2 to 0 in stack } for(int i=siz-1;i>=0;i--) { if(s.empty()==1) { s.push(nums[i]); v.push_back(-1); } else { while(s.empty()!=1 && (s.top()

[@spandanrastogi7144]

Awesome explanation ! In Code, I think by mistake Loop is iterating from left to right when it should be iterating from right to left.

[@sypher4735]

Yes, you're right, but he actually mentioned it in the comment.

[@spandanrastogi7144]

Didn't saw that

[@udayptp]

Bhai kal hi mere coding round mein ye question pucha tha, 1- next greater element 2- make largest no using all element of the array

[@chandankumarshaw216]

which company

[@udayptp]

@@chandankumarshaw216 Thinkitive technologies

[@udayptp]

@@chandankumarshaw216 package 4.5lpa

[@Carson00_11]

@@udayptp bhai abhe kya kar rhe ho

[@udayptp]

@@Carson00_11 D. E. Shaw and Co.

[@somratdutta]

I wish we had such teachers! 😢😍

[@protyaybanerjee5051]

Concept - Monotonic Stack. Here we are using Monotonically Decreasing stack

[@onlygaming24-h7d]

i was at dp 55 i was suggested to watch largest rectangle in histogram and there i was suggested to watch first the next greater element so this is how i am here. Now i will watch this then i will again go to largest rectangle in histogram and then where i was originally exactly to DP 55

[@ineerajnishad]

Maaannn, Striver you're certainly best in what you do, which is TEACH things so so smoothly! Big thanks Sir❤

[@rishabhkumar8115]

bro hats off to you...you have brought this new institution for circular array..Before this I don't about this. Thankx to be our menntor

[@gowthamarun43]

we can try the same logic by traversing from the end also like normal array variant

[@omkarsk98]

Excellently explained why removing the element wont affect the solution for previous elements

[@ayush_Bhagat129]

class Solution { public: vector nextGreaterElements(vector& nums) { int n = nums.size(); stack st; vector Nge(n, -1); for (int i = 2 * n - 1; i >= 0; i--) { while (!st.empty() && st.top()

[@stormwalker1130]

Watched your n queen and sudoku problem,the explanation was awesome.

[@snehilsinha4689]

Best possible explanation! The concept gets stuck in my mind forever after watching this 🔥. tysm striver bhaiya 💓

[@vitaminprotein2217]

leetcode 1019 cpp sol:(of linkedlist) vectorans; stackst; //convert the LL in ans(array/vector) while(head){ ans.push_back(head->val); head=head->next; } //now it became a normal array q for(int i=ans.size()-1;i>=0;i--){ while(!st.empty() && st.top()=0;i--){ while(!st.empty() && st.top()

[@adarshbadagala]

Thank you so much for such an excellent explanation but I have small doubt instead of writing an if condition inside loop can we just use i%n for nge too? i mean instead of writing if(i

[@JujareVinayak]

Yes

[@arjunrai8126]

Yes u can

[@AbhishekKumar-vr7sh]

U can and it will still pass the test cases but its not needed bcoz anyways its gonna get replaced when we process elements in range i = 0 to n-1

[@adarshbadagala]

@@AbhishekKumar-vr7sh thank you for clarifying

[@varun1017]

16:40 I think iteration should be done in reverse order. forward is not working for me.

[@cricedge4454]

bhai for(i=2*n-1 .......) hoga ..but u have written for(i=0..)

[@humble.660]

CODE in Python: class Solution: def nextGreaterElements(self, nums: List[int]) -> List[int]: res = [-1] * len(nums) n = len(nums) stack = [] for i in range(2 * len(nums) - 1, - 1, - 1): while stack and nums[i % n] >= stack[-1]: stack.pop() if stack: res[i % n] = stack[-1] stack.append(nums[i % n]) return res

[@vishnupandey3390]

thanks man it really helped me 🙏

[@swastikkumarpal7795]

bhaiya there is something wrong in the for condition ...it should start iterating from backward

[@karanthakkar9009]

Hii bhaiya, recently I came into a problem called "Sherlock and the maze" tags: memorization & DP. I really did not understood how to slove problem, when I saw the editorial it was really confusing, I also saw other's people submission, but everyone had submitted in scala,haskell language. Could you make a video on that problem?

[@ashwanisingh1135]

saw the title , went to solve the problem and then came back here to see the best approach

[@anubhavsingh8144]

Great work bhaiya I have a request to make bhaiya Pls make a video on "Find K closest elements" Using Binary Search.. Leetcode: 658

[@chetanraghavv]

class Solution { public: vector findClosestElements(vector& arr, int k, int x) { int n = arr.size(); if(n == 1) return arr; vector res; int start = 0, end = n-1, mid=0; while(start =0 && end=0) //means end pointer is exhausted, select elements from start in this case { res.push_back(arr[start]); start--; k--; } while(k>0 && end

[@Chhooso]

im dry running so times but still didnt understand how that code works under circular condition it will work without that condition and in coding ninjas too that condition is not mentioned ig idk y whenever i start from the end i just get it -1 after dry running and the rest is correct

[@Chhooso]

my bad got it...never doubt striver

[@AishwarysinghEC]

why(i

[@Anonymous-uj3jx]

Hello Striver! Thanks for all your videos. Can you please upload a video on the problem "Sort A Stack" which is in SDE sheet. It is really tough to understand😢

[@athxrva_n]

yeah man babbar had taught it with recusion but i did'nt understand the whole recursion properly

[@MyPathUnveiledYT]

in circular array method i think answer should be like 10 12 -1 11 -1 not 10 12 --1 11 -1

[@bhaveshkumar6842]

Thank you, Striver!!! You're the best!!

[@surajsah3361]

in explanation you iterate from index of last element and in code you are itterating from starting element?

[@rakib_8feb]

13:10 Circular Array

[@ritesh1211]

int n = arr.size(); vectorans(n,-1); stackstk; //dec to find next greater for(int i=0;iarr[stk.top()]){ int poped = stk.top(); ans[poped]=arr[i%n]; stk.pop(); } stk.push(i%n); //pushing indexs } return ans;

[@stith_pragya]

Thank You So Much Striver Brother.....🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@ayeshasumaiya8280]

Very clear and detailed explanation I thought my brain cannot understand the logic behind this simple problem but your explanation made it crystal clear

[@LifeGoing]

There is no doubt that your explanation is awesome.but it would much better if you will show code in code editor.

[@takeUforward]

Okay lets try that

[@LifeGoing]

@@takeUforward hopefully it will be more understandable 😍

[@aniketpandey1913]

Hi Guys, problem : find next greater element to the right in array Solution: we use stack for solving this Doubt : some people prefer to store indices rather than the actual element in the stack can someone pls explain why the first approach is better than the other. One advantage i can think of is that in case of storing indices we save space

[@DR-mq1le]

doesnt matter since integer will anyways take the same space(as indices and elements both are int type) , if say the elements were some other bigger data type than int , then it would make sense storing indices , but then also negligible difference would be there

[@suryapriya1953]

Bro please teach us with a small example with 11 elements . it ll be efficient to understand to beginners with 5 to 6 elements.

[@samjackson4982]

can anyone answer, why we are going through the array in reverse order? what is the intuition?

[@swaroopchakraborty3488]

Great tutorial Striver. God bless you. I tried optimizing the solution for circular structure a little bit more if array lengths are short (n 0 && n != arr.length) { return null; } int[] nge = new int[1]; if (arr.length > 0 && arr.length < 2) { nge[0] = -1; return nge; } if (arr.length == 2) { nge = new int[2]; if (arr[0] < arr[1]) { nge[0] = arr[1]; nge[1] = -1; } else { nge[0] = -1; nge[1] = arr[0]; } return nge; } // The Stacking Algorithm will work only if there are more than 2 elements in // array. This is // done for reducing space and time complexity for arrays which are less than // n=2 in length or are relatively small. nge = new int[n]; Stack st = new Stack(); // Circular array implementation 2n-1 for (int i = 0; i < 2 * n - 1; i++) { // n-1 while (!st.empty() && st.firstElement()

[@pryansh_]

you are the best on YT..

[@ronakslibrary8635]

Thanks sir for explaining this concept , the use of Stack is improvinzing the efficiency of solution by lot

[@AshishKumar-pq6pr]

Awesome lecture bhaiya

[@selvaragavan_10]

Bro you're starting from zero and how does it checks the next greater element???

[@gaganeshmahajan7198]

Can someone please explain why he took the loop till 2n-1?? I didnt understand..Please help..

[@BRSanush]

Wow what an explaination. Thank you striver.

[@adityasethi9794]

I think code has an error. Why do we start form left and go till right. Aren't we supposed to start from end and do i-- ?

[@MuhammadFahreza]

what is the time complexity on 12:16? Thanks!

[@sasanknvs5603]

I think the for loop is wrong. Since we are iterating from right, we should start the for loop from i=2n-1. It was correctly implemented on the C++/Java code links in the description

[@rachitgupta4143]

u can also start from i=0 dude

[@igaming_]

We have to make i%n for every i except for for loop Am I right guuys reply...

[@Rituresh]

bhaiya aaj ya question smajh mai aa gaya aapki viddeo sai.you are doing good eork

[@whatthecode7219]

Solved this question 2 days back, nonetheless, enjoyed the explanation :)

[@111rhishishranjan2]

I didn't get that why you used circular array and made the solution difficuilt to understand . mean normal array also work well i guess.If anyone understood it , kindly explain me too , //Here is my code #include using namespace std; vector nextGreaterElement(vector v){ int n=v.size(); vectorarr1(n,0) ; stacks; for(int i=n-1;i>=0;i--){ //int currentprice=v[i]; while(!s.empty() and s.top()

[@srinathchembolu7691]

he explained a total of 2 questions. The circular array one is next greater element II on leetcode

[@pankajkumarshukla9253]

Your teaching ability is awesome ,bro keep it up.

[@KoushikVarma-h1b]

Next greater element for 7 is 10 not -1. 3:47

[@SatyamKumar-bw4vi]

Hare Krishna!

[@PIYUSH-lz1zq]

for first variant why we running for 2*n-1 ... it should be done only for circular onces !!

[@gauravmutha2536]

@@PIYUSH-lz1zq Did you get the answer,I too am facing same problem.

[@googlysahoo1397]

For the first variant, the size of the array will be n then why and how we will take 2n-1?? Though for 2nd variant we are copying the elements(imaginary) we will assume the size to be 2n-1 but not in the first case. Could anyone explain the reason??

[@takeUforward]

In first case, we don’t have the circular array concept. If there does not exists on right, its -1

[@googlysahoo1397]

My doubt is why to run the loop from 0 to 2n-1 where the size of the array is n? for(int i = 2n-1; i >= 0; i++) // this line

[@ritishgupta2982]

@@googlysahoo1397 do i--

[@gauravmutha2536]

Did you get your answer?

[@sidarthroy815]

so after i>n there will be empty iteration(with just pushing nd poping in stack) for rest half till it reaches 2n-1?

[@amanbhadani8840]

Yes,basically for i>=n its just pushing and popping,but this step will ensure that if there is any element greater than last index element present on the left side,it will be already there in stack. And for i

[@ApnaVlogs-tj7do]

Wonderful explanation bhaiya

[@rohith8269]

Greeeaaaaaaattt explanation!!!! Thankyou so much

[@umangjaiswal7448]

for circular , can we use upper_bound to solve problem ??

[@gauravmehra8189]

did you find the answer to your question? can we use upper_bound for circular?

[@nishantjarang7302]

can you make a video,how to reverse a linkedlist of group of given size

[@doctordsa8669]

This is one of the best videos I have watched on the internet

[@amandubey5287]

This is just amazing and very well explained. Thanks

[@JosepJeev]

Shdnt i be as I=2*n-1 instead of i=0

[@amanbhadani8840]

Amazing explanation !!

[@dpxy1599]

nicely explained

[@rgvhere]

u watch showing time 3:23 bro

[@securelyinsaycure]

Smooth like butter 🧈

[@kamleshjoshi2949]

Waah jo doubt aya whi btadiya 😅 OP 🔥🔥

[@alexmercerind]

modulo logic is cool

[@LaxmiTeja-c2f]

You are a saviour!!

[@franciskp9117]

Bro In the first few minutes of the video you are iterating the array from right to left, but when the sudo code is shown, you start 'i' from 0 and go till 2n-1. Isn't this the other way around ? Like shouldn't 'i' start from 2n-1 and end at i >= 0. Correct me if I'm wrong.

[@Shubham-zl1zb]

Thank you

[@youtubeuserlovesyoutube2207]

striver bro the loop cond should be for (int i = (len * 2) - 1; i >= 0; i--) Isn't it>?

[@sp_9467]

Yes you are right

[@adarshrai9516]

Thanks bro ❤️

[@bhagirathmakwana9112]

my brother u are great

[@satyampande684]

understood!!

[@raghavendrasoni6712]

great explanation man!

[@sivaganesh4489]

initially i worried about the run time of the video. after watching the video, i enjoyed every second of it. really great explanation dude.

[@PIYUSH-lz1zq]

for first variant why we running for 2*n-1 ... it should be done only for circular onces !!

[@amanbhadani8840]

@@PIYUSH-lz1zq yes

[@abinvarkey2331]

best video on the topic i could find!

[@abd6406]

"for' loop will be on reverse

[@shubhamgupta9778]

Thank u bro.... Your video always give us very good concept..... Please make a session on josephus problem. This problem is very easy to understand but hard to implement.

[@shrikantsharma8933]

Hi, I really like your videos, just 1 question, which software or tool you are using to put these small animations on prerecorded videos?

[@damandeepsingh6037]

great explanantion

[@abhaysharma4065]

Thanks sir 😊

[@shivamehta6537]

Awesome👍

[@chaitanyakumar9229]

no yaar 😂😂

[@shubhambhatt2704]

How do you even come up with these solutions?

[@leepakshiyadav1643]

Excellent explanation :)

[@kainathussain6973]

god level explaination🤩😍

[@yeswanthh5068]

Understood sir

[@azraazra8273]

Sir please put this in a seperate palylist

[@takeUforward]

Already done, check stack queue playlist

[@Learnprogramming-q7f]

Thank you Bhaiya

[@aryanchauhan8066]

nice concept