One thing I can say is GeeksforGeeks is not making the videos to the expectations people have. I see a lot of videos in this playlist where either the instructor is just dry running or reading out the solution than explaining the intuition /reason behind it
The pseudocode for Step 2, sub-step 5 is wrong, regarding "then push the popped element back". It should be "then push next into the stack". So basically the stack is used to keep all the scanned elements whose GNE are yet unknown.
i think the complexity of the 2nd approach is only O(2n) because at worst case if all element is in decreasing order like for example:15,13,11,3 it will push all of them to stack because condition (element < next) is not correct so the stack will be fall ,then the finally while loop will pop the element from stack and set the next to -1 for all elements.
i think we can do it using arrays also where each element stores the index of the next greatest element. we can fill this array from right to left. time complexity is O(n) and space complexity also would be O(n)
IF we have elements as 4, 8, 6,25 it says(in stack method) push 4 in stack and them compare 8 to 4 if 8 is grater then it is the NGE for 4 but this is wrong the NGE for 4 is 6. Am I thinking correct or plz someone correct me....
The problem statement states that the Next greater Element for an element x is the first greater element on the right side of x in array. Hope this solves your confusion. :)
We can peek() top and check if top is less than next. We won't need to push back again in this case. My java code - private static void printNGE(Stack stack, int arr[]) { if(arr == null) return;
stack.push(arr[0]);
for(int i = 1; i < arr.length; i++) { int next = arr[i];
if(!stack.isEmpty() && stack.peek().getData() < next) { int element = stack.pop().getData(); while(element < next) { System.out.println("NGE for " + element + " is " + next); if(stack.isEmpty()) break; element = stack.pop().getData(); } }
stack.push(next); } while(!stack.isEmpty()) { System.out.println("NGE for " + stack.pop().getData() + " is -1"); }
Java version of the code public static void getNGE(int[] a) { Stack s = new Stack(); s.push(a[0]); for (int i = 1; i < a.length; i++) { if (s.peek() != null) { while (true) { if (s.peek() == null || s.peek() > a[i]) { break; } System.out.println(s.pop() + ":" + a[i]); } } s.push(a[i]); } while (s.peek() != null) { System.out.println(s.pop() + ":" + -1); } }
We should also make check for empty stack using s.isEmpty(), so code should be public static void getNGE(int[] a) { Stack s = new Stack(); s.push(a[0]); for (int i = 1; i < a.length; i++) { if (s.peek() != null) { while (true) { if (s.isEmpty() || s.peek() == null || s.peek() > a[i]) { break; } System.out.println(s.pop() + ":" + a[i]); } } s.push(a[i]); } while (!s.isEmpty() && s.peek() != null) { System.out.println(s.pop() + ":" + -1); } }
One thing I can say is GeeksforGeeks is not making the videos to the expectations people have. I see a lot of videos in this playlist where either the instructor is just dry running or reading out the solution than explaining the intuition /reason behind it
What if, our output must be in same order or sequence as that of input array, then how indexing will be done?
one question ... WHY do you need to push elements out of the stack to compare them ? you can use can't u use s.top() ?
the pseudo code of method 2 doesn't mention about pushing next and when to do it.
What if you solve this problem using queue instead of stack ?
I have doubt if that if my array is 100, 99, 98, 97, ......, 50, 121, 49, 48, 47, ......., 3, 2, 1, 120 then how it is still O(n)?
The pseudocode for Step 2, sub-step 5 is wrong, regarding "then push the popped element back". It should be "then push next into the stack". So basically the stack is used to keep all the scanned elements whose GNE are yet unknown.
i think the complexity of the 2nd approach is only O(2n)
because at worst case if all element is in decreasing order like for example:15,13,11,3
it will push all of them to stack because condition (element < next) is not correct
so the stack will be fall ,then the finally while loop will pop the element from stack and set the next to -1 for all elements.
Not working for 7 8 1 4 (using Stack)
Instead we can start finding NGE from end of array using stack just like previous video in this tutorial
Its quite simple than that given in video
indeed my friend.
I thought just the same way as you thought ;)
it more efficient and easier
why can't we iterate from the end of the array?
problem implementation using stack at 12:40 (skipped basic stack operation)
doesn't the second method require more space?
I think so because in 2nd algorithm we are using linked list to create stack which consumes more space than an array in 1st algorithm
i think we can do it using arrays also where each element stores the index of the next greatest element. we can fill this array from right to left. time complexity is O(n) and space complexity also would be O(n)
i dont think so.....
@harish Joshi. You are correct. We can't do using array. I was in different understanding of problem statement earlier.
nice article
Why do i feel like it's harkirat explaining this video
IF we have elements as 4, 8, 6,25 it says(in stack method) push 4 in stack and them compare 8 to 4 if 8 is grater then it is the NGE for 4 but this is wrong the NGE for 4 is 6. Am I thinking correct or plz someone correct me....
The problem statement states that the Next greater Element for an element x is the first greater element on the right side of x in array.
Hope this solves your confusion. :)
GeeksforGeeks yes thanks I got it...
yes thsnks...
It seems Shushant Singh Rajput is explaining !!
We can peek() top and check if top is less than next. We won't need to push back again in this case. My java code -
private static void printNGE(Stack stack, int arr[]) {
if(arr == null) return;
stack.push(arr[0]);
for(int i = 1; i < arr.length; i++) {
int next = arr[i];
if(!stack.isEmpty() && stack.peek().getData() < next) {
int element = stack.pop().getData();
while(element < next) {
System.out.println("NGE for " + element + " is " + next);
if(stack.isEmpty()) break;
element = stack.pop().getData();
}
}
stack.push(next);
}
while(!stack.isEmpty()) {
System.out.println("NGE for " + stack.pop().getData() + " is -1");
}
Here is the solution :
czcams.com/users/timedtext_cs_panel?c=UCninsT8lEtwlJYedzYY7bnA&tab=2
Java version of the code
public static void getNGE(int[] a) {
Stack s = new Stack();
s.push(a[0]);
for (int i = 1; i < a.length; i++) {
if (s.peek() != null) {
while (true) {
if (s.peek() == null || s.peek() > a[i]) {
break;
}
System.out.println(s.pop() + ":" + a[i]);
}
}
s.push(a[i]);
}
while (s.peek() != null) {
System.out.println(s.pop() + ":" + -1);
}
}
Thank you, Abhijit! :)
I've shared this with our content team.
We should also make check for empty stack using s.isEmpty(), so code should be
public static void getNGE(int[] a) {
Stack s = new Stack();
s.push(a[0]);
for (int i = 1; i < a.length; i++) {
if (s.peek() != null) {
while (true) {
if (s.isEmpty() || s.peek() == null || s.peek() > a[i]) {
break;
}
System.out.println(s.pop() + ":" + a[i]);
}
}
s.push(a[i]);
}
while (!s.isEmpty() && s.peek() != null) {
System.out.println(s.pop() + ":" + -1);
}
}
way of explanation is not good
Goddammit, man that accent is painful to listen to
find the next greatest element for each element in the array
input 8 5 9 2 3
output 9 8 -1 3 5