L6. Next Greater Element - II | Stack and Queue Playlist

[@Demon01Editz]

we can do it with below code also it is using same concept but we will simply start with max element in array (because we know that its NGE will be -1 and we know that if we don't find any other element who is greater than our current element then we know maxelement will be our answer) then we will traverse through other elements like NGE-I video(because we know the ending) class Solution { public: vector nextGreaterElements(vector& nums) { int maxele = INT_MIN; int maxidx = -1; int n = nums.size(); for(int i=0;i(maxidx-n-1);i--){ int idx = i; if(idx nums[idx]){ nge[idx] = st.top(); st.push(nums[idx]); } else{ while(!st.empty() && st.top()

[@onelove177]

Literally I have at least 10 videos to get this but I didn't get! But sir Striver!😍 Thank you!

[@Kshitijsingh-n7f]

MY APPROACH--> approach-1(optimal) TC-O(3N) SC-O(2N) [including memory for storing returning answer] //push all ele from n-2 to start then traverse from the n-1 to the start in similar way as NGE 1 problem since in NGE 1 problem we didnt have any greater ele for the last so we started from last and just check next left and left updating the their maxes but here since last ele can also have the NGE so we have put all elements that can be NGE of last ele then we do like normal NGE 1 problem solution vector nextGreaterElements(vector& nums) { stacks; int n=nums.size(); vectorv(n); for(int i=n-2;i>=0;i--){ s.push(nums[i]); } for(int i=n-1;i>=0;i--){ while(!s.empty() && s.top()

[@ashmitshelke1444]

thats what I did too

[@crazybro4383]

Tried question for 15 minutes, not able to solve so I thought soln dekh leta hu starting ke question dekhne padte hai to understand how the approaches work for a particular data structure.............aapki vid kholi you didn't even explained the question, at time stamp 1:00 I paused the vid and solved the question myself, felt good........abse roz dsa grind hoga 3rd sem aa gya thodi fatri hai for placements and internship vaise hi tier3 clg h

[@Jai_Shri_Krishna_Shri_radhe]

@Take you forward Small optimisation :- Why we even need to push 2n elements push only till (i < n) Then we would not waste extra time in pushing and popping...

[@atulwadhwa192]

The better solution was the goto hint to approach the optimal approach. Striver OP 🔥

[@pullurupraveen9315]

we can put the all the elements in order expect the last element to get compared then perform the operation using the NGE (using the stack)here the time complexity at worst case becomes like 0(2n+1) and space complexity also 0(n+2).

[@amanasrani6405]

Thank You So Much Sir for this Amazing Lecture

[@SomrikTapaswi]

loved the way you made us understand !

[@parth2439]

understood, Thank you striver !

[@alonbrim]

Very clear explanation! Thanks a lot!

[@closer9689]

CODE => class Solution { public: //Better Approach :-> without making extra circular array vector nextGreaterElements(vector& nums) { int n = nums.size(); stack st; for(int i = n-2 ; i >= 0; --i) { st.push(nums[i]); } vector result; for(int i = n-1 ; i>= 0 ; --i) { int curr = nums[i]; while ( !st.empty() && st.top()

[@apmotivationakashparmar722]

Thank you for excellent explaination.

[@jenishadsouza907]

Excellent explanation!

[@Akash-Bisariya]

very nicely explained 😍😍

[@aravatanish3170]

Striver please upload Heap series

[@alessandrocamilleri1239]

Thank you and great explanation. Can't you just traverse the array circularly in reverse from the max element index? That way you would just add an O(n) to the original TC of NGE1. I coded it as follows: vector nextGreaterElements(vector& nums) { int n = nums.size(); int maxIndex = 0; for (int i = 1; i < n; i++) // ADDITIONAL O(n) if (nums[i] > nums[maxIndex]) maxIndex = i; stack st; vector nge(n); for (int i = maxIndex; i > maxIndex - n; i--) { int j = (n + i) % n; while (!st.empty() && st.top()

[@vaarigupta6332]

Awesome explaination

[@shubhamlifearts8138]

Thanks bhaiya for great content ❤

[@atulwadhwa192]

My approach: class Solution { private: void findNgeForLastEle(vector &nums,int n,stack &st,vector &res){ // int nge = -1; for(int i=n-2;i>=0;i--){ if(nums[i]>nums[n-1]) st.push(nums[i]); } if(!st.empty()) res[n-1] = st.top(); st.push(nums[n-1]); } public: vector nextGreaterElements(vector& nums) { stack st; int n = nums.size(); vector res(n,-1); findNgeForLastEle(nums,n,st,res); for(int i = n-2;i>=0;i--){ while(!st.empty() && st.top()

[@rushidesai2836]

Smart solution. Wow.

[@amankumarsingh3995]

Excellent video

[@agneshk1012]

class Solution { public int[] nextGreaterElements(int[] nums) { int n = nums.length; int[] nge = new int[n]; Stack stack = new Stack(); for(int i=2*n-1; i>=0; i--) { int index = i%n; while(!stack.isEmpty() && nums[index] >= stack.peek()) stack.pop(); if(stack.empty()) nge[index] = -1; else nge[index] = stack.peek(); stack.push(nums[index]); } return nge; } }

[@sauravfarkade1928]

Thankyou bhaiya!!

[@abhaykumarsingh3884]

Steps 1. Just put all element from end in stack first. 2. Now perform same operations as you have performed in Next-Greater Element-I You don't need to think about hypothical array

[@adilahmed6730]

I also thought of the same method

[@Ekam873]

great method

[@chiragmaheshwari6761]

what is thought process behind it intiutiton can u please explain me brother

[@shikher4559]

great observation!

[@shivam_prakash_0108]

excellent explanation

[@SoulFrmTitanic]

guys jo for the first time stacks and queues kr raha h, kya tumse ye questions khud se ho paate hn ? Please batana!! kyuki mujhse literally nhi hopaate!! hn, ek aad baar meri approach jrur same hojaati h striver bhaiya jesi

[@ashwani6527]

For beginners the best way is to watch and learn then understand then revise

[@SoulFrmTitanic]

@@ashwani6527 ok bhaiya!!

[@ashutoshyadav9881]

kisi se nhi hote jab tak us type ke question na kiye ho

[@tusharsingh1257]

Completed 19th July

[@priyapathak9716]

Implement Queue using Stacks put this one also! thnku

[@SibiRanganathL]

Understood

[@pruthvinarayana9568]

⭐⭐Solution in Python: Can Also be Sovled Like This: class Solution: def nextGreaterElements(self, nums: List[int]) -> List[int]: stack = [] n = len(nums) res = [-1] * n for i in range(2*n): index = i%n # Here the Cur is the Index , NOT the current Value. while stack and nums[index] > nums[stack[-1]]: res[stack[-1]] = nums[index] stack.pop() stack.append(index) return res

[@oyeesharme]

thanks bhai

[@DeadPoolx1712]

UNDERSTOOD;

[@ryanv7535]

Isn't the space complexity O(n)? Say the stack contains some element a, after which there are some elements and then a is pushed into stack again. When that occurs all elements from top to a will be popped. So there can never be more than n elements in the stack, is what I think. Please correct me if I'm making a mistake.

[@Gurunat16]

Same thoughts!

[@KartikeyTT]

tysm sir

[@AradhyaVerma-p3m]

BRUTEFORCE: ***JAVA*** class Solution { public int findGreater(int index,int value,int []nums){ for(int i=index;i

[@omkarshendge5438]

you forgot to reverse the ans vector by the way, like that is how i got all cases passed.

[@akhilesh_ku]

Nah not needed 😊

[@ashu_10011]

that is needed only when you are using push_back or emplace_back functions to add elements in the answer vector

[@adilahmed6730]

@@ashu_10011 what's the alternate method to add to the vector array?

[@barathkumarg9197]

public static void findNextGreater(int[] inputArray, int[] output){ Stack stack = new Stack(); //Iterate the input Array for (int index=inputArray.length -1 ;index>=0;index--){ //pop the highest elements while(!stack.isEmpty() && inputArray[index] > stack.peek()) stack.pop(); //stack empty case if (stack.isEmpty()) { stack.push(inputArray[index]); output[index] = -1; } // else we found the next greater element just push to stack and output array else{ output[index] = stack.peek(); stack.push(inputArray[index]); } } } i think these one worked for me, which is simple, no need of double iteration, if i am wrong please correct me, Thanks !!!

[@vinit_notfound]

❤❤❤❤

[@amankumarsingh3995]

❤

[@shreyxnsh.14]

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

[@omkarshendge5438]

you need to reverse the ans array too

[@esco0p210]

@@omkarshendge5438 take vector ans (n,-1) it will be reversed

[@skasrafali8707]

@@omkarshendge5438 yes you are right

[@IshraqTanvir]

his explanaition is too well.........................................................................but, it would be better if he don't write pseudocode and write real code

[@sohaildarwajkar9979]

Then u would complain about the language in which he is writing the code..Grow Up man!!

[@IshraqTanvir]

@@sohaildarwajkar9979 actually I won't ....... ...... cause most of the cpp mans whether like java or c++.......both the language is much closer syntaxically......

[@talkswithprabh5374]

If you know the logic and pseudo code, its too easy to write code. Its all about syntax then.

[@aryankumar3018]

Understood

[@CS090Srikanth]

❤

[@rutujashelke4208]

Understood