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

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

[@jatinsaini2914]

brother kya phadate ho app bhaut hi sahi..👌

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

[@yoddha621]

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

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

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

[@krrishlather6521]

should include the code also

[@kingkohli7175]

amazing💯

[@DeadPoolx1712]

UNDERSTOOD;

[@kaustubhgaikwad2562]

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

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

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

[@SibiRanganathL]

Understood

[@shivisingh9975]

Understood!

[@akashdevmore4447]

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

[@Abhi_9478]

mind blowing

[@NiteshMaurya1111]

thanks bhaiya

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

[@anuranpradhan]

song name in the last?

[@nayankhuman1043]

understood :)

[@KartikeyTT]

tysm sir

[@debadityaghosh7612]

great

[@sauravfarkade7032]

Understood!!

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

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

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