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.

[@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

[@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()

[@somratdutta]

I wish we had such teachers! 😢😍

[@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.

[@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

[@protyaybanerjee5051]

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

[@snehilsinha4689]

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

[@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

[@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.

[@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 🙏

[@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

[@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

[@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?

[@cricedge4454]

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

[@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()

[@ashwanisingh1135]

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

[@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()

[@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

[@AishwarysinghEC]

why(i

[@Rituresh]

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

[@bhaveshkumar6842]

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

[@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

[@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

[@stith_pragya]

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

[@pryansh_]

you are the best on YT..

[@rakib_8feb]

13:10 Circular Array

[@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-- ?

[@kamleshjoshi2949]

Waah jo doubt aya whi btadiya 😅 OP 🔥🔥

[@AshishKumar-pq6pr]

Awesome lecture bhaiya

[@BRSanush]

Wow what an explaination. Thank you striver.

[@ronakslibrary8635]

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

[@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;

[@swastikkumarpal7795]

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

[@selvaragavan_10]

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

[@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 😍

[@doctordsa8669]

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

[@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

[@ApnaVlogs-tj7do]

Wonderful explanation bhaiya

[@MyPathUnveiledYT]

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

[@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.

[@pankajkumarshukla9253]

Your teaching ability is awesome ,bro keep it up.

[@varun1017]

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

[@rohith8269]

Greeeaaaaaaattt explanation!!!! Thankyou so much

[@whatthecode7219]

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

[@surajsah3361]

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

[@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.

[@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?

[@anurondas3853]

Man... Guys stop paying thousand of rupees for learning to code!! Striver over here does it better than any and all of them! Really great video.😆😁

[@amandubey5287]

This is just amazing and very well explained. Thanks

[@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.

[@dpxy1599]

nicely explained

[@amanbhadani8840]

Amazing explanation !!

[@utkarshgupta3869]

Hello bhaiya, I have one question... please reply... I am a B.Sc(c.s) Student. Please help me to know can I get a job(above 5 lpa) after my Graduation. I learnt enough C++ and completed DSA and going to start web development and also 3 star at codechef. I can learn anything for job after Graduation. Please help to me tell that can I get or I have to do MCA.

[@Sarojkumar-yh9uy]

Just start applying to relevant job openings

[@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

[@bhagirathmakwana9112]

my brother u are great

[@securelyinsaycure]

Smooth like butter 🧈

[@raghavendrasoni6712]

great explanation man!

[@abinvarkey2331]

best video on the topic i could find!

[@satyampande684]

understood!!

[@Shubham-zl1zb]

Thank you

[@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

[@gaganeshmahajan7198]

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

[@adarshrai9516]

Thanks bro ❤️

[@samjackson4982]

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

[@chaitanyakumar9229]

no yaar 😂😂

[@igaming_]

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

[@KoushikVarma-h1b]

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

[@alexmercerind]

modulo logic is cool

[@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

[@Learnprogramming-q7f]

Thank you Bhaiya

[@leepakshiyadav1643]

Excellent explanation :)

[@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.

[@damandeepsingh6037]

great explanantion

[@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?

[@shivamehta6537]

Awesome👍

[@abhaysharma4065]

Thanks sir 😊

[@MuhammadFahreza]

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

[@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

[@kainathussain6973]

god level explaination🤩😍

[@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?

[@mohithguptakorangi1766]

ok, so you have written the code wrong?? cause i=2n-1 should be the initialized, I've been cracking my head

[@takeUforward]

Please watch the video completely… i%n has been used.. no need to initialize..

[@mohithguptakorangi1766]

@@takeUforward I meant (i=2n-1; i>=0;i--) the way you wrote in github code.....OR both are correct?

[@takeUforward]

Oops, my bad.. github is correct!

[@mohithguptakorangi1766]

@@takeUforward Ok cool....I watch your videos completely see?? so I'm getting better than you haha. Have a good day

[@takeUforward]

@@mohithguptakorangi1766 haha, actually while writing code, i need to explain, see in camera, hence concentration XD

[@JosepJeev]

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

[@yeswanthh5068]

Understood sir

[@aryanchauhan8066]

nice concept

[@abd6406]

"for' loop will be on reverse

[@rgvhere]

u watch showing time 3:23 bro

[@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

[@shubham6215]

Thanks 🤩