Next Greater Element 1 (LeetCode 496) | Full solution with examples and animation | Study Algorithms

Given an array of integers that can be in any order, you need to return the index of the next greater element to the right of every element. A very fun problem to solve as soon as you visualize the correct data structure to use. A stack comes in very handy whenever you see a nested loop, or you need to iterate from the backward direction again and again. Watch the video to understand the concept and the approach along with a dry-run of code in JAVA.

Chapters:
00:00 - Intro
00:59 - Problem statement and description
03:37 - A Brute Force approach to find the Next Greater Element
06:51 - Efficient Way to find the Next Greater Element
11:42 - Dry-run of Code
14:06 - Final Thoughts

📚 Links to topics I talk about in the video:

📖 Reference Books:

🎥 My Recording Gear:

💻 Get Social 💻

#leetcode #programming #interview

[TufanPandu]

After watching my expensive course i come to watch this video and it's OSM!

[bonafontciel]

I was able to type my own code just with your explanation. Thanks!

[dharmeshkase]

the way you explain everything is just

[shristipurusarthi]

The explanation of a solution is when we can code it just by watching the explanation. thanks a lot for the amazing content brother

[yashgarg]

really like your energy and you make it easy to understand nikhil
keep it up,

[Hayat]

i never thought this could be that simple, thanku sir

[NerchukoMava]

Underrated channel, sir please make more videos, you have the potential to be on top.

[lakcai]

Great explanation! Clear and intuitive!

[varsshhaa]

omg!! I am happy that I have found this channel !! explanation is simply great !! Looking forward to more such videos !!

[prasadm]

Great explanation. Thank you so much Nikhil

[srikrishna_ss]

Your Way Of Explanation Simply Awesome 🤗

[pietech]

while forming a new array with stack store original array element index into map then traverse num2 and get the index of elements from hash and look the value at that index in fresh Array

[sammedpatil]

what will be space and time space complexity if we are using stack and Map??

[Sonu]

sir aap bahut hi gjb tarike se samjhaye ek baar me hi samjh aa gya thanku so much sir

[pradheeshkumar-vp]

That was a crystal clear explanation !!

[tanishktripathi]

This is such a nice explanation, Here is the Java simplified solution


class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
HashMap<Integer, Integer> map = new HashMap<>();
Stack<Integer> stack = new Stack<>();

for(int i=nums2.length-1; i>=0; i--) {
while(!stack.isEmpty() && stack.peek()<nums2[i]){
stack.pop();
}
if(stack.size()>0) {
map.put(nums2[i], stack.peek());
}
else {
map.put(nums2[i], -1);
}
stack.push(nums2[i]);
}

int[]res = new int[nums1.length];
for(int i =0; i<nums1.length; i++) {
res[i] = map.get(nums1[i]);
}
return res;
}
}

[andretheruler]

thank you, i was a bit confused until you explained it

[sahithd]

loved the way you explain the problem!

[ardtierguy]

UPDATED SOLUTION(LEETCODE SOLUTION)
JUST USE ONLY MAP
vector<int> nums1, vector<int>& nums2) {
unordered_map<int, int>m;
stack<int>s;
int n=nums2.size();
m[nums2[n-1]]=-1;
s.push(nums2[n-1]);
for(int i=nums2.size()-2;i>=0;i--)
{

{
m[nums2[i]]=s.top();
s.push(nums2[i]);
continue;
}

s.pop();
if(s.empty())
{
m[nums2[i]]=-1;
s.push(nums2[i]);
}
else if(s.top())
{
m[nums2[i]]=s.top();
s.push(nums2[i]);
}
}
for(int i=0;i<nums1.size();i++)
{
nums1[i]=m[nums1[i]];
}
return nums1;
}
};

THANKS ME BY LINKING MY SOLUTION ACTUALLY BHAIYA SOLVE QUESTION ACCORDING TO QUESTION ON GFG

[vilakshan.s]

I think time complexity will still be O(n^2) where in worst case we will end up emptying the whole stack in order to find next greater element for ith position