L5. Next Greater Element | Stack and Queue Playlist

[@akhilesh_ku]

For leetcode's 496 it has two arrays , first just make nge for nums2 then take map and maps indexes of nums1 in nums2 then find it's value from nge vector nextGreaterElement(vector& nums1, vector& nums2) { int n = nums1.size(); int m = nums2.size(); vector nexti(m,-1); vector ans; unordered_map mp; stack st; st.push(-1); for(int i=m - 1;i>=0;i--){ while(!st.empty() && st.top()

[@DhananjayKumar-bd2jg]

No need to create extra vector to store the index, just put in the map where key is array element and value is next greater element.

[@SibiRanganathL]

Useful

[@anishaa3298]

UNDERSTOOD!!!!!!!!!

[@harshuke5831]

Understood ❤

[@DhananjayKumar-bd2jg]

Solution for the leetcode :) vector nextGreaterElement(vector& nums1, vector& arr) { stack st; unordered_map m; int n = arr.size(); for(int i = n-1; i >= 0; i--){ while(!st.empty() && st.top() < arr[i]) st.pop(); if(st.empty()) m[arr[i]] = -1; else m[arr[i]] = st.top(); st.push(arr[i]); } vector ans; for(int i = 0; i < nums1.size(); i++){ ans.push_back(m[nums1[i]]); } return ans; }

[@yoddha621]

Such easy solution, can't come up with this.

[@parth2439]

understood, Thank you

[@jatinsaini2914]

brother kya phadate ho app bhaut hi sahi..👌

[@closer9689]

CODE => class Solution { public: //Better Approach :- T.C => O(n+m), S.C => O(n) vector nextGreaterElement(vector& nums1, vector& nums2) { int m = nums1.size(); int n = nums2.size(); unordered_map mp; /*for(int i = 0 ; i < m ; ++i) //No need to store nums1 element , in map, WHY? beacause , no need to check for element of nums2 , whether it is in nums1 or not { mp[nums1[i]] = -1; } */ stack st; for(int i = n-1 ; i >= 0 ; --i ) //traversing the nums2 backwards { int curr = nums2[i]; while( !st.empty() && st.top() < curr ) { st.pop(); } //If Not empty//top is ans//If empty//-1 is ans mp[curr] = !st.empty() ? st.top() : -1; //first check if stack is empty or not st.push(curr); } vector result; for(int i = 0 ; i < m ; ++i) { result.push_back(mp[nums1[i]]); } return result; } };

[@foodiepanda6281]

Thanks for the video

[@chitranshverma1822]

in brute force approach you didnt noted anything about -1 in answer....the case when there is nothing larger that the current one in nums

[@personadevwithhitsat7277]

Assign the whole array with -1

[@xperthighlight]

after the loop you can add assign in to -1 ; if loops doesn't break than it will get assigned -1

[@shashankshukla7989]

JAVA BRUTEFORCE class Solution { public int nextGreater(int[] arr, int num) { int n = arr.length; for(int i=0; i

[@AftabNaik]

This can also be implemented in linear time without using a stack Instead of maintaining a stack, we can say nge(i) = i+1 by default and then let's check if it's actually the case If yes then well n good Else we can say that nge(i) = nge(i+1) again check if its true or not, if its not then we will just check for nge(nge(i+1)) This will keep the range amortized and hence the time complexity will be O(n) Iterative implementation would be nge[i] = i+1; while(nge[i]>=nge[i+1]) { if(nge[i]==n)break; nge(i) = nge[nge[i]]; }

[@kingkohli7175]

amazing💯

[@SibiRanganathL]

Understood

[@DeadPoolx1712]

UNDERSTOOD;

[@shivisingh9975]

Understood!

[@ashishlesnar9577]

for java solution public int[] nextGreaterElement(int[] nums1, int[] nums2) { Map map = new HashMap(); Stack stack = new Stack(); int n = nums1.length; int[] ans = new int[n]; for (int num : nums2) { while (!stack.isEmpty() && stack.peek() < num) map.put(stack.pop(), num); stack.push(num); } for (int i = 0; i < nums1.length; i++) { ans[i] = map.getOrDefault(nums1[i], -1); } return ans; }

[@Abhi_9478]

mind blowing

[@NiteshMaurya1111]

thanks bhaiya

[@chitranshverma1822]

the leetcode question includes circular array ..bhaiya how to deal with it??

[@anm9992]

In reverse order first store all elements in stack then use ngr

[@SarojVerma-z7q]

LeetCode's 496. Next Greater Element I class Solution { public: vector nextGreaterElement(vector& nums1, vector& nums2) { vector res; int i = 0; while(i < nums1.size()) { int pos2 = 0; for(int j=0; j

[@sauravfarkade1928]

Understood!!

[@kaustubhgaikwad2562]

If I have 1 then next greater to it will be 2 not 3 tests cases are failing

[@debadityaghosh7612]

great

[@nayankhuman1043]

understood :)

[@KartikeyTT]

tysm sir

[@rohitroy20786]

496. Next Greater Element I class Solution { public: vector nextGreaterElement(vector& nums1, vector& nums2) { int n=nums2.size(); stack st; map mpp; for(int i=n-1;i>=0;i--){ while(!st.empty() && nums2[i]>=st.top()){ st.pop(); } if(st.empty()){ mpp[nums2[i]]=-1; } else{ mpp[nums2[i]]=st.top(); } st.push(nums2[i]); } vector ans; for(int i=0;i

[@akashdevmore4447]

can any one explain tc of optimal soln is O(2n) not O(n^2)?

[@anuranpradhan]

song name in the last?

[@krrishlather6521]

should include the code also

[@kartikverma6412]

code :- class Solution { public: vector nextGreaterElement(vector& nums1, vector& nums2) { //monotonic stack-- ele are stored in a specific order stack st; unordered_map mp; //reverse order traversal for(int i=nums2.size()-1;i>=0;i--){ while(!st.empty() && st.top()

[@surajbkunte7672]

vector nextGreaterElement(vector& nums1, vector& nums2) { map mpp; stack stk; for (int i = nums2.size() - 1; i >= 0; i--) { while (!stk.empty() && nums2[i] >= stk.top()) { stk.pop(); } if(stk.empty()){ mpp[nums2[i]] = -1; } else{ mpp[nums2[i]] = stk.top(); } stk.push(nums2[i]); } for (int i = 0; i < nums1.size(); i++) { nums1[i] = mpp[nums1[i]]; } return nums1; }

[@rohitraj-df8qs]

why so less views

[@vrajpatel9259]

this entire playlist is uploaded a day ago.

[@alm7677]

Green looks 🤢 good

[@oyeesharme]

thanks bhaiya

[@aryankumar3018]

Understood

[@rutujashelke4208]

Understood