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
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 :)
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.
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();
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
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()
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 }
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?
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
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😢
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
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
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.
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()
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
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.
//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()
Very clear and detailed explanation I thought my brain cannot understand the logic behind this simple problem but your explanation made it crystal clear
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
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??
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
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
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
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()
I think the for loop is wrong. Since we are iterating from right, we should start the for loop from i=2n-1. It was correctly implemented on the C++/Java code links in the description
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.
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 }
Great explaination. Although won't the Time complexity be O(n^2) as for loop is running for n and while loop at the worst case will run for n elements as well. Thus, n*n = n^2. Someone kindly explain if I m thinking in wrong direction.
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
I am in comment section just to check that if I am only not understanding or the code had mistakes.. thanks for this
@@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.
Thanks @Striver
Correction 1 - for(int i=((2*n)-1); i>=0 ; i--)
Correction 2 - while( (!stack.isEmpty()) && (stack.peek()
😄
This mistake wasted so much of my time
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 :)
> I have been a TA at coding ninjas
literally nobody asked
so a coding ninja TA also using free resources 😂😂
@@mudrad1930 There always something new to learn
no more learning from coding ninja
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.
thanks for that tip :)
woah really nice intuition!! thanks
thanks so much !! that's an awesome intuition !!
the loop cond should be
for (int i = (len * 2) - 1; i >= 0; i--)
yes, u r right.
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;
}
thanks bro
for first variant why we running for 2*n-1 ... it should be done only for circular onces !!
@@PIYUSH-lz1zq no for first run for n-1 to 0 only
This code allows same values to be reassigned,thats not logical and not prefered.
Awesome explanation !
In Code, I think by mistake Loop is iterating from left to right when it should be iterating from right to left.
Yes, you're right, but he actually mentioned it in the comment.
Didn't saw that
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
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()
In Next Greater Elements problem I guess instead of i
for first variant why we running for 2*n-1 ... it should be done only for circular onces !!
@@PIYUSH-lz1zq Not required for first variant bro.
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()
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
which company
@@chandankumarshaw216 Thinkitive technologies
@@chandankumarshaw216 package 4.5lpa
@@udayptp bhai abhe kya kar rhe ho
@@Carson00_11 D. E. Shaw and Co.
bhai for(i=2*n-1 .......) hoga ..but u have written for(i=0..)
Maaannn, Striver you're certainly best in what you do, which is TEACH things so so smoothly! Big thanks Sir❤
I wish we had such teachers! 😢😍
Best possible explanation! The concept gets stuck in my mind forever after watching this 🔥. tysm striver bhaiya 💓
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?
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
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-- ?
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
Yes
Yes u can
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
@@AbhishekKumar-vr7sh thank you for clarifying
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😢
yeah man babbar had taught it with recusion but i did'nt understand the whole recursion properly
Bro you're starting from zero and how does it checks the next greater element???
we can try the same logic by traversing from the end also like normal array variant
Watched your n queen and sudoku problem,the explanation was awesome.
bhaiya there is something wrong in the for condition ...it should start iterating from backward
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
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
my bad got it...never doubt striver
Excellently explained why removing the element wont affect the solution for previous elements
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.
saw the title , went to solve the problem and then came back here to see the best approach
Concept - Monotonic Stack. Here we are using Monotonically Decreasing stack
There is no doubt that your explanation is awesome.but it would much better if you will show code in code editor.
Okay lets try that
@@takeUforward hopefully it will be more understandable 😍
why(i
Hi, I really like your videos, just 1 question, which software or tool you are using to put these small animations on prerecorded videos?
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()
Can someone please explain why he took the loop till 2n-1?? I didnt understand..Please help..
Thank you, Striver!!! You're the best!!
Great work bhaiya
I have a request to make bhaiya
Pls make a video on "Find K closest elements" Using Binary Search..
Leetcode: 658
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
in explanation you iterate from index of last element and in code you are itterating from starting element?
Thank You So Much Striver Brother.....🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
16:40
I think iteration should be done in reverse order. forward is not working for me.
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.
Just start applying to relevant job openings
can anyone answer, why we are going through the array in reverse order? what is the intuition?
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()
Very clear and detailed explanation I thought my brain cannot understand the logic behind this simple problem but your explanation made it crystal clear
ok, so you have written the code wrong?? cause i=2n-1 should be the initialized, I've been cracking my head
Please watch the video completely… i%n has been used.. no need to initialize..
@@takeUforward I meant (i=2n-1; i>=0;i--)
the way you wrote in github code.....OR both are correct?
Oops, my bad.. github is correct!
@@takeUforward Ok cool....I watch your videos completely see?? so I'm getting better than you haha. Have a good day
@@mohithguptakorangi1766 haha, actually while writing code, i need to explain, see in camera, hence concentration XD
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()
bhaiya aaj ya question smajh mai aa gaya aapki viddeo sai.you are doing good eork
Thanks sir for explaining this concept , the use of Stack is improvinzing the efficiency of solution by lot
Wow what an explaination.
Thank you striver.
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
thanks man it really helped me 🙏
Shdnt i be as I=2*n-1 instead of i=0
We have to make i%n for every i except for for loop
Am I right guuys reply...
Bro please teach us with a small example with 11 elements . it ll be efficient to understand to beginners with 5 to 6 elements.
what is the time complexity on 12:16? Thanks!
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??
In first case, we don’t have the circular array concept. If there does not exists on right, its -1
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
@@googlysahoo1397 do i--
Did you get your answer?
This is one of the best videos I have watched on the internet
Solved this question 2 days back, nonetheless, enjoyed the explanation :)
you are the best on YT..
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
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
Awesome lecture bhaiya
so after i>n there will be empty iteration(with just pushing nd poping in stack) for rest half till it reaches 2n-1?
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
Waah jo doubt aya whi btadiya 😅 OP 🔥🔥
in circular array method i think answer should be like 10 12 -1 11 -1 not 10 12 --1 11 -1
Your teaching ability is awesome ,bro keep it up.
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()
he explained a total of 2 questions. The circular array one is next greater element II on leetcode
striver bro
the loop cond should be
for (int i = (len * 2) - 1; i >= 0; i--)
Isn't it>?
Yes you are right
for circular , can we use upper_bound to solve problem ??
did you find the answer to your question? can we use upper_bound for circular?
This is just amazing and very well explained. Thanks
I think the for loop is wrong. Since we are iterating from right, we should start the for loop from i=2n-1. It was correctly implemented on the C++/Java code links in the description
u can also start from i=0 dude
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.
can you make a video,how to reverse a linkedlist of group of given size
In while loop its showing stackempty error and the flow is not going to the if statement.please rply
The code in the description has been tested , please refer it :)
Wonderful explanation bhaiya
Greeeaaaaaaattt explanation!!!! Thankyou so much
How do you even come up with these solutions?
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;
how come i is starting from 0. I didn't get it.
best video on the topic i could find!
initially i worried about the run time of the video. after watching the video, i enjoyed every second of it. really great explanation dude.
for first variant why we running for 2*n-1 ... it should be done only for circular onces !!
@@PIYUSH-lz1zq yes
13:10 Circular Array
Amazing explanation !!
Smooth like butter 🧈
Next greater element for 7 is 10 not -1. 3:47
Great explaination. Although won't the Time complexity be O(n^2) as for loop is running for n and while loop at the worst case will run for n elements as well. Thus, n*n = n^2. Someone kindly explain if I m thinking in wrong direction.
Same question, did you got any answer for this . this was the reason I wasn't able to solve this problem as the required complexity is O(n)
Hare Krishna!
for first variant why we running for 2*n-1 ... it should be done only for circular onces !!
@@PIYUSH-lz1zq Did you get the answer,I too am facing same problem.
u watch showing time 3:23 bro
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.😆😁
Bhaiya shuruwat s kaise declare krte h stack, vector sb woh sb bhi padhaye toh hm jaise bccho k liye useful hoga
for first variant why we running for 2*n-1 ... it should be done only for circular onces !!
great explanation man!
Excellent explanation :)
i could able to find dp for this
You are a saviour!!
Bro u live in sonapur na??
No
@@takeUforward then where in kolkata?
Sir please put this in a seperate palylist
Already done, check stack queue playlist
"for' loop will be on reverse
my brother u are great
god level explaination🤩😍
nicely explained
Thank you
Thanks bro ❤️