L5. Next Greater Element | Stack and Queue Playlist

[@himanshu788]

KeyPoint: Use the example of light Pole to visualize the solution

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

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

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

[@amitpathak475]

explaination worth the time.

[@vishnu9134]

what an explanation !!😍😍😍

[@iamnoob7593]

Wow brilliant , Thank you striver

[@anishaa3298]

UNDERSTOOD!!!!!!!!!

[@harshuke5831]

Understood ❤

[@parth2439]

understood, Thank you

[@yoddha621]

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

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

[@khushisharma-tp7ff]

thank u great explanation

[@kingkohli7175]

amazing💯

[@foodiepanda6281]

Thanks for the video

[@jatinsaini2914]

brother kya phadate ho app bhaut hi sahi..👌

[@krishnaagrawal5335]

HELLO BROTHER AAP YAHAN BHI?

[@jatinsaini2914]

@@krishnaagrawal5335 Or Kaha ?

[@dineshlalam15]

I didn't understand the O(2N) logic. Someone please explain

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

[@impatientgaming9868]

v good explanation

[@mathsworldbysuraj6278]

BRUTE FORCE
vector arr;
int n1=nums1.size();
int n2=nums2.size();
for(int i=0;i

[@anuranpradhan]

song name in the last?

[@payal_singh18]

inspiration, by unknown brain

[@hfactor1932]

Awsm

[@Abhi_9478]

mind blowing

[@NiteshMaurya1111]

thanks bhaiya

[@KartikeyTT]

tysm sir

[@shivisingh9975]

Understood!

[@SibiRanganathL]

Understood

[@sauravfarkade1928]

Understood!!

[@kaustubhgaikwad2562]

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

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

[@DeadPoolx1712]

UNDERSTOOD;

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

[@payal_singh18]

two pointer approach

[@akashdevmore4447]

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

[@noface-qs5yi]

Do you encounter each element twice at max O(2*n) or you take each element almost n times O(n*n)

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

[@nayankhuman1043]

understood :)

[@debadityaghosh7612]

great

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

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

[@pratikhajare228]

for Java bruit force solution :-
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {

int n1 = nums1.length;
int n2= nums2.length;
int nge [] = new int[n1];
for(int i=0; i

[@krrishlather6521]

should include the code also

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

[@sumairakhurram2478]

But for time complexity there are maximum 1 2 3 4 5 ...pops so 1+2+3+4+....N = N(N+1)/2 which is O(N²)

[@Xloachtop]

No, he explains this in the video. Each element will only at max be popped once, because each element will be pushed at max one time. This means that maximum n elements can be popped throughout the entire execution.

[@nehasagi2169]

wow

[@rohitraj-df8qs]

why so less views

[@vrajpatel9259]

this entire playlist is uploaded a day ago.

[@alm7677]

Green looks 🤢 good

[@oyeshxrme]

thanks bhaiya

[@aryankumar3018]

Understood

[@rutujashelke4208]

Understood

[@abhinavabhi3568]

Understood

[@bindushree1021]

Understood

[@fanofabdevillersandmathslo5960]

Understood