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--){
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()
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).
@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...
14:43 why would the space complexity be 0(2N)? Shouldn't it be O(N) as only those many elements that are in the array can be in stack at a given point?
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
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()
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.
Hello everyone, my placements are starting in March 2025. I have started learning DSA using the TakeUforward SDE sheet and have completed the first 10 problems. However, I was able to understand only 3 of them, and I am struggling to build logic on my own. I am unsure if I am on the right track or where to start. Could you please give me some advice on how to approach solving problems independently and where I should begin? I have programming knowledge but need guidance. I am not aiming to join a big MNC company, but I want to prepare effectively.
⭐⭐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
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
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
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 !!!
his explanaition is too well.........................................................................but, it would be better if he don't write pseudocode and write real code
@@sohaildarwajkar9979 actually I won't ....... ...... cause most of the cpp mans whether like java or c++.......both the language is much closer syntaxically......
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()
Literally I have at least 10 videos to get this but I didn't get! But sir Striver!😍 Thank you!
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()
thats what I did too
This too taking TC O(4n) bro!!
In worst case, That while takes tottally pop() atmost 2n elements from the stack
loved the way you made us understand !
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).
@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...
Brilliant explanation . Thanks striver
The better solution was the goto hint to approach the optimal approach. Striver OP 🔥
Very clear explanation! Thanks a lot!
14:43 why would the space complexity be 0(2N)? Shouldn't it be O(N) as only those many elements that are in the array can be in stack at a given point?
I was also thinking the same
yeah, i think even the time complexity should be about O(3N) and not 4N
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
understood, Thank you striver !
Thank You So Much Sir
for this Amazing Lecture
Striver please upload Heap series
Excellent explanation!
Thank you for excellent explaination.
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()
Awesome explaination
very nicely explained 😍😍
Excellent video
Thanks bhaiya for great content ❤
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()
Smart solution. Wow.
Thankyou bhaiya!!
excellent explanation
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.
Same thoughts!
Hello everyone, my placements are starting in March 2025. I have started learning DSA using the TakeUforward SDE sheet and have completed the first 10 problems. However, I was able to understand only 3 of them, and I am struggling to build logic on my own. I am unsure if I am on the right track or where to start. Could you please give me some advice on how to approach solving problems independently and where I should begin? I have programming knowledge but need guidance. I am not aiming to join a big MNC company, but I want to prepare effectively.
hey karthi
Completed 19th July
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;
}
}
Understood
⭐⭐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
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()
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
I also thought of the same method
great method
what is thought process behind it intiutiton can u please explain me brother
great observation!
Implement Queue using Stacks put this one also! thnku
thanks bhai
UNDERSTOOD;
tysm sir
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()
you need to reverse the ans array too
@@omkarshendge5438 take vector ans (n,-1) it will be reversed
@@omkarshendge5438 yes you are right
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
For beginners the best way is to watch and learn then understand then revise
@@ashwani6527 ok bhaiya!!
kisi se nhi hote jab tak us type ke question na kiye ho
you forgot to reverse the ans vector by the way, like that is how i got all cases passed.
Nah not needed 😊
that is needed only when you are using push_back or emplace_back functions to add elements in the answer vector
@@ashu_10011 what's the alternate method to add to the vector array?
BRUTEFORCE: ***JAVA***
class Solution {
public int findGreater(int index,int value,int []nums){
for(int i=index;i
❤❤❤❤
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 !!!
I impleted a better approach than raj bhaiya with TC= O(3n) myself-
class Solution {
public:
vector nextGreaterElements(vector& nums) {
stack st;
queue q;
int n = nums.size();
vector ans(n);
for(int i=0; i=0; i--){
while(!st.empty() && nums[i]>= st.top()){
st.pop();
}
if(st.empty()){
st.push(nums[i]);
while(!q.empty() && nums[i]>=q.front()){
q.pop();
}
if(q.empty()){
ans[i] = -1;
}
else{
ans[i] = q.front();
}
}
else{
ans[i] = st.top();
st.push(nums[i]);
}
}
return ans;
}
};
❤
VERY HARD TO UNDERSTAND
KUCH SAMAJH NAHI AAYA
his explanaition is too well.........................................................................but, it would be better if he don't write pseudocode and write real code
Then u would complain about the language in which he is writing the code..Grow Up man!!
@@sohaildarwajkar9979 actually I won't ....... ...... cause most of the cpp mans whether like java or c++.......both the language is much closer syntaxically......
If you know the logic and pseudo code, its too easy to write code. Its all about syntax then.
abe bhai...bina logic ke code kr rha h...code rataa hua h tereko
Understood
❤
Understood
Understood