Next Greater Element | Two Variants | Leetcode

Find DSA, LLD, OOPs, Core Subjects, 1000+ Premium Questions company wise, Aptitude, SQL, AI doubt support and many other features that will help you to stay focussed inside one platform under one affordable subscription. Have a hassle free one stop solution for up-skilling and preparing.

[takeUforward]

While writing code, it should have been.. 2n-1 to 0 😅

[nikhilpatro]

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 :)

[kritidiptoghosh]

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.

[nayanbhuyan]

To make things even more simpler, if(i < n) condition is not required, instead write i % 2 in other steps, like:
vector<int> nums)
{
int n = nums.size();
vector<int> res(n);
stack<int> 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;
}

[spandanrastogi]

Awesome explanation !
In Code, I think by mistake Loop is iterating from left to right when it should be iterating from right to left.

[harshalgarg]

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<int> v)
{
vector<int> vans;
int n = v.size();
stack<int> 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()<=v[i])
st.pop();

if(st.empty())
vans.push_back(-1);

else
vans.push_back(st.top());

st.push(v[i]);
}

reverse(vans.begin(), vans.end());

return vans;
}

[maccall]

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.

vector<int>v;
stack<int>s;

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()<=nums[i]))
{
s.pop();
}
if(s.empty())
{
v.push_back(-1);
s.push(nums[i]);
}
else
v.push_back(s.top()), s.push(nums[i]);
}
}
reverse(v.begin(), v.end()); // reverse vector
return v;

[thor]

the loop cond should be
for (int i = (len * 2) - 1; i >= 0; i--)

[adwiteek]

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 you can directly return the vector on leetcode when you will be iterating from i<n

[akshaykenjale]

In Next Greater Elements problem I guess instead of i <= 2n - 1, we can directly write as i < 2n.
Video at 17:30

[ineerajnishad]

Maaannn, Striver you're certainly best in what you do, which is TEACH things so so smoothly! Big thanks Sir❤

[snehilsinha]

Best possible explanation! The concept gets stuck in my mind forever after watching this 🔥. tysm striver bhaiya 💓

[udayptp]

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

[rishabhkumar]

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

[adarshbadagala]

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<n) {
if(!st.empty()) nge[i] = st.top();
}
can't we directly write if ( !st.empty() ) nge[ i % n ] = st.top()
Thanks in advance

[Anonymous-ujjx]

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😢

[humble.]

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

[ayush_Bhagat]

class Solution {
public:
vector<int> nums) {
int n = nums.size();
stack<int> st;
vector<int> Nge(n, -1);

for (int i = 2 * n - 1; i >= 0; i--) {
while (!st.empty() && st.top() <= nums[i % n]) {
st.pop();
}

if (!st.empty()) {
Nge[i%n] = st.top();
}

st.push(nums[i % n]);
}
return Nge;
}
};

[tusharprajapati]

These are the four conditions
// We can change it to next smaller elements
//next greater from left
Slight change
We are storing index of arr in the stack.
1: iterate from last
2: while(!st.isEmpty() && arr[st.peek()] >= arr[i])
//Simply pop
sr pop();
3: if( st.isEmpty())
{
nextgrtr [i]= -1;
} else{
nextgrtr [i] = arr[st.peek()];
}
4: st.push(i);
Dry run with pen and paper

[gowthamarun]

we can try the same logic by traversing from the end also like normal array variant