For leetcode's 496 it has two arrays , first just make nge for nums2 then take map and maps indexes of nums1 in nums2 then find it's value from nge vector nextGreaterElement(vector& nums1, vector& nums2) { int n = nums1.size(); int m = nums2.size(); vector nexti(m,-1); vector ans; unordered_map mp; stack st; st.push(-1); for(int i=m - 1;i>=0;i--){ while(!st.empty() && st.top()
int m = nums1.size(); int n = nums2.size(); unordered_map mp; /*for(int i = 0 ; i < m ; ++i) //No need to store nums1 element , in map, WHY? beacause , no need to check for element of nums2 , whether it is in nums1 or not { mp[nums1[i]] = -1; } */
stack st; for(int i = n-1 ; i >= 0 ; --i ) //traversing the nums2 backwards { int curr = nums2[i];
for java solution public int[] nextGreaterElement(int[] nums1, int[] nums2) { Map map = new HashMap(); Stack stack = new Stack(); int n = nums1.length; int[] ans = new int[n]; for (int num : nums2) { while (!stack.isEmpty() && stack.peek() < num) map.put(stack.pop(), num); stack.push(num); } for (int i = 0; i < nums1.length; i++) { ans[i] = map.getOrDefault(nums1[i], -1); } return ans; }
LeetCode's 496. Next Greater Element I class Solution { public: vector nextGreaterElement(vector& nums1, vector& nums2) { vector res; int i = 0; while(i < nums1.size()) { int pos2 = 0; for(int j=0; j
code :- class Solution { public: vector nextGreaterElement(vector& nums1, vector& nums2) { //monotonic stack-- ele are stored in a specific order stack st; unordered_map mp; //reverse order traversal for(int i=nums2.size()-1;i>=0;i--){ while(!st.empty() && st.top()
This can also be implemented in linear time without using a stack Instead of maintaining a stack, we can say nge(i) = i+1 by default and then let's check if it's actually the case If yes then well n good Else we can say that nge(i) = nge(i+1) again check if its true or not, if its not then we will just check for nge(nge(i+1)) This will keep the range amortized and hence the time complexity will be O(n) Iterative implementation would be nge[i] = i+1; while(nge[i]>=nge[i+1]) { if(nge[i]==n)break; nge(i) = nge[nge[i]]; }
No, he explains this in the video. Each element will only at max be popped once, because each element will be pushed at max one time. This means that maximum n elements can be popped throughout the entire execution.
For leetcode's 496 it has two arrays , first just make nge for nums2 then take map and maps indexes of nums1 in nums2 then find it's value from nge
vector nextGreaterElement(vector& nums1, vector& nums2) {
int n = nums1.size();
int m = nums2.size();
vector nexti(m,-1);
vector ans;
unordered_map mp;
stack st;
st.push(-1);
for(int i=m - 1;i>=0;i--){
while(!st.empty() && st.top()
No need to create extra vector to store the index, just put in the map where key is array element and value is next greater element.
Useful
KeyPoint: Use the example of light Pole to visualize the solution
Solution for the leetcode :)
vector nextGreaterElement(vector& nums1, vector& arr) {
stack st;
unordered_map m;
int n = arr.size();
for(int i = n-1; i >= 0; i--){
while(!st.empty() && st.top() < arr[i]) st.pop();
if(st.empty()) m[arr[i]] = -1;
else m[arr[i]] = st.top();
st.push(arr[i]);
}
vector ans;
for(int i = 0; i < nums1.size(); i++){
ans.push_back(m[nums1[i]]);
}
return ans;
}
in brute force approach you didnt noted anything about -1 in answer....the case when there is nothing larger that the current one in nums
Assign the whole array with -1
after the loop you can add assign in to -1 ;
if loops doesn't break than it will get assigned -1
JAVA BRUTEFORCE
class Solution {
public int nextGreater(int[] arr, int num) {
int n = arr.length;
for(int i=0; i
explaination worth the time.
CODE =>
class Solution {
public:
//Better Approach :- T.C => O(n+m), S.C => O(n)
vector nextGreaterElement(vector& nums1, vector& nums2) {
int m = nums1.size();
int n = nums2.size();
unordered_map mp;
/*for(int i = 0 ; i < m ; ++i) //No need to store nums1 element , in map, WHY? beacause , no need to check for element of nums2 , whether it is in nums1 or not
{
mp[nums1[i]] = -1;
}
*/
stack st;
for(int i = n-1 ; i >= 0 ; --i ) //traversing the nums2 backwards
{
int curr = nums2[i];
while( !st.empty() && st.top() < curr )
{
st.pop();
}
//If Not empty//top is ans//If empty//-1 is ans
mp[curr] = !st.empty() ? st.top() : -1; //first check if stack is empty or not
st.push(curr);
}
vector result;
for(int i = 0 ; i < m ; ++i)
{
result.push_back(mp[nums1[i]]);
}
return result;
}
};
Wow brilliant , Thank you striver
what an explanation !!😍😍😍
Such easy solution, can't come up with this.
UNDERSTOOD!!!!!!!!!
for java solution
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map map = new HashMap();
Stack stack = new Stack();
int n = nums1.length;
int[] ans = new int[n];
for (int num : nums2) {
while (!stack.isEmpty() && stack.peek() < num)
map.put(stack.pop(), num);
stack.push(num);
}
for (int i = 0; i < nums1.length; i++) {
ans[i] = map.getOrDefault(nums1[i], -1);
}
return ans;
}
brother kya phadate ho app bhaut hi sahi..👌
HELLO BROTHER AAP YAHAN BHI?
@@krishnaagrawal5335 Or Kaha ?
the leetcode question includes circular array ..bhaiya how to deal with it??
In reverse order first store all elements in stack then use ngr
Understood ❤
LeetCode's 496. Next Greater Element I
class Solution {
public:
vector nextGreaterElement(vector& nums1, vector& nums2) {
vector res;
int i = 0;
while(i < nums1.size())
{
int pos2 = 0;
for(int j=0; j
v good explanation
code :-
class Solution {
public:
vector nextGreaterElement(vector& nums1, vector& nums2) {
//monotonic stack-- ele are stored in a specific order
stack st;
unordered_map mp;
//reverse order traversal
for(int i=nums2.size()-1;i>=0;i--){
while(!st.empty() && st.top()
BRUTE FORCE
vector arr;
int n1=nums1.size();
int n2=nums2.size();
for(int i=0;i
thank u great explanation
This can also be implemented in linear time without using a stack
Instead of maintaining a stack, we can say nge(i) = i+1 by default
and then let's check if it's actually the case
If yes then well n good
Else we can say that nge(i) = nge(i+1) again check if its true or not, if its not then we will just check for nge(nge(i+1))
This will keep the range amortized and hence the time complexity will be O(n)
Iterative implementation would be
nge[i] = i+1;
while(nge[i]>=nge[i+1]) {
if(nge[i]==n)break;
nge(i) = nge[nge[i]];
}
two pointer approach
If I have 1 then next greater to it will be 2 not 3 tests cases are failing
Thanks for the video
amazing💯
for Java bruit force solution :-
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int n1 = nums1.length;
int n2= nums2.length;
int nge [] = new int[n1];
for(int i=0; i
understood, Thank you
Awsm
song name in the last?
inspiration, by unknown brain
496. Next Greater Element I
class Solution {
public:
vector nextGreaterElement(vector& nums1, vector& nums2) {
int n=nums2.size();
stack st;
map mpp;
for(int i=n-1;i>=0;i--){
while(!st.empty() && nums2[i]>=st.top()){
st.pop();
}
if(st.empty()){
mpp[nums2[i]]=-1;
}
else{
mpp[nums2[i]]=st.top();
}
st.push(nums2[i]);
}
vector ans;
for(int i=0;i
mind blowing
thanks bhaiya
Understood!
UNDERSTOOD;
Understood!!
Understood
can any one explain tc of optimal soln is O(2n) not O(n^2)?
Do you encounter each element twice at max O(2*n) or you take each element almost n times O(n*n)
But for time complexity there are maximum 1 2 3 4 5 ...pops so 1+2+3+4+....N = N(N+1)/2 which is O(N²)
No, he explains this in the video. Each element will only at max be popped once, because each element will be pushed at max one time. This means that maximum n elements can be popped throughout the entire execution.
tysm sir
vector nextGreaterElement(vector& nums1, vector& nums2) {
map mpp;
stack stk;
for (int i = nums2.size() - 1; i >= 0; i--) {
while (!stk.empty() && nums2[i] >= stk.top()) {
stk.pop();
}
if(stk.empty()){
mpp[nums2[i]] = -1;
}
else{
mpp[nums2[i]] = stk.top();
}
stk.push(nums2[i]);
}
for (int i = 0; i < nums1.size(); i++) {
nums1[i] = mpp[nums1[i]];
}
return nums1;
}
should include the code also
understood :)
great
wow
why so less views
this entire playlist is uploaded a day ago.
Green looks 🤢 good
thanks bhaiya
Understood
Understood
Understood
Understood