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...
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.
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
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
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 !!!
⭐⭐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
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
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).
loved the way you made us understand !
@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...
Very clear explanation! Thanks a lot!
The better solution was the goto hint to approach the optimal approach. Striver OP 🔥
Thank you for excellent explaination.
Striver please upload Heap series
Awesome explaination
Excellent explanation!
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()
very nicely explained 😍😍
Smart solution. Wow.
Excellent video
excellent explanation
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()
Thankyou bhaiya!!
Thanks bhaiya for great content ❤
Implement Queue using Stacks put this one also! thnku
thanks bhai
Completed 19th July
UNDERSTOOD;
Understood
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;
}
}
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()
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!
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?
tysm sir
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!
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 !!!
⭐⭐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
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
❤❤❤❤
❤
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.
Understood
❤
Understood