LeetCode 496 - Next Greater Element I
LeetCode 503 - Next Greater Element II
Key Point: Using data structure: Stack
When find a bigger element, set NGE for all elements previously that is smaller than current element
Method 2 (Using Stack)
1) Push the first element to stack.
2) Pick rest of the elements one by one and follow following steps in loop.
....a) Mark the current element as next.
....b) If stack is not empty, then pop an element from stack and compare it with next.
....c) If next is greater than the popped element, then next is the next greater element fot the popped element.
....d) Keep poppoing from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements
....g) If next is smaller than the popped element, then push the popped element back.
3) After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them.
http://www.ideserve.co.in/learn/next-great-element-in-an-array
https://prismoskills.appspot.com/lessons/Arrays/Next_largest_element_for_each_element.jsp
http://codingloverlavi.blogspot.com/2014/11/next-greater-element.html
Next larger element for each element
void printNextLarger (int arr[])
{
if (arr.length <= 0)
return;
Stack stack = new Stack ();
stack.push (arr[0]);
for (int i=1; i < arr.length; i++)
{
int curr = arr[i];
while (stack.empty() == false)
{
int leftEle = stack.pop();
if (leftEle < curr)
{
print (leftEle + " -- next larger element -- >" + currEle);
// This loop prints and discards all local pairs whose next larger has been found.
}
else
{
stack.push (leftEle);
break;
}
}
// current element's next larger element is yet to be seen, so current element always goes into the stack.
stack.push(curr);
}
// The elements left in the stack have no next larger element.
// Infact, the leftovers are arranged in sorted order in the stack due to this.
while (stack.empty() == false)
{
int leftoverEle = stack.pop();
print (leftoverEle + " -- next larger element -- > None");
}
}
https://github.com/Simiopolis/careercup-java/blob/master/src/paypal/PPReplaceQ.java
* Link: http://www.careercup.com/question?id=6497025214382080
* Replace element of an Array with nearest bigger number at right
* side of the Array in O(n)
*
* For example if the input Array is
* 7, 5, 6, 3, 4, 1, 2, 9, 11
* output array should be
* 9, 6, 9, 4, 9, 2, 9, 11, 11
public static void replace(int[] a) {
int i=0;
// Find nearest bigger number in linear time.
// Update indices when found.
for(int j=1; j<a.length; j++) {
if(a[i] < a[j]) {
a[i] = a[j];
i++;
j = i;
}
}
// Print function for testing purposes.
for(Integer in : a) {
System.out.print(in+" ");
}
System.out.println();
}
http://www.crazyforcode.com/replace-element-next-greatest-array/
Related: Replace every element with the next greatest
Read full article from Next Greater Element | GeeksforGeeks
LeetCode 503 - Next Greater Element II
Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.
Examples:
a) For any array, rightmost element always has next greater element as -1.
b) For an array which is sorted in decreasing order, all elements have next greater element as -1.
c) For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows.
a) For any array, rightmost element always has next greater element as -1.
b) For an array which is sorted in decreasing order, all elements have next greater element as -1.
c) For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows.
Element NGE 4 --> 5 5 --> 25 2 --> 25 25 --> -1
When find a bigger element, set NGE for all elements previously that is smaller than current element
Method 2 (Using Stack)
1) Push the first element to stack.
2) Pick rest of the elements one by one and follow following steps in loop.
....a) Mark the current element as next.
....b) If stack is not empty, then pop an element from stack and compare it with next.
....c) If next is greater than the popped element, then next is the next greater element fot the popped element.
....d) Keep poppoing from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements
....g) If next is smaller than the popped element, then push the popped element back.
3) After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them.
http://www.ideserve.co.in/learn/next-great-element-in-an-array
https://prismoskills.appspot.com/lessons/Arrays/Next_largest_element_for_each_element.jsp
Time Complexity is O(n) because each element is pushed 1 time and popped 1 time from the stack.
Space Complexity is O(n)
Space Complexity is O(n)
public static void printNextGreaterElement(int[] input) { Stack<Integer> stack = new Stack<Integer>(); int inputSize = input.length; stack.push(input[0]); for (int i = 1; i < inputSize; i++) { while (!stack.isEmpty() && stack.peek() < input[i]) { System.out.println("Next greater element for " + stack.pop() + "\t = " + input[i]); } stack.push(input[i]); } while (!stack.isEmpty()) { int top = (int) stack.pop(); System.out.println("Next greater element for " + top + "\t = " + null); } } static void printNGE(int arr[], int n) { int i = 0; stack s = new stack(); s.top = -1; int element, next; /* push the first element to stack */ s.push(arr[0]); // iterate for rest of the elements for (i = 1; i < n; i++) { next = arr[i]; if (s.isEmpty() == false) { // if stack is not empty, then // pop an element from stack element = s.pop(); /* If the popped element is smaller than next, then a) print the pair b) keep popping while elements are smaller and stack is not empty */ while (element < next) { System.out.println(element + " -- " + next); if (s.isEmpty() == true) break; element = s.pop(); } /* If element is greater than next, then push the element back */ if (element > next) s.push(element); } /* push next to stack so that we can find next greater for it */ s.push(next); } /* After iterating over the loop, the remaining elements in stack do not have the next greater element, so print -1 for them */ while (s.isEmpty() == false) { element = s.pop(); next = -1; System.out.println(element + " -- " + next); } }
How to get elements in same order as input?
The above approach may not produce output elements in same order as input. To achieve same order, we can traverse the same in reverse order
The above approach may not produce output elements in same order as input. To achieve same order, we can traverse the same in reverse order
void printNextLarger (int arr[])
{
if (arr.length <= 0)
return;
Stack stack = new Stack ();
stack.push (arr[0]);
for (int i=1; i < arr.length; i++)
{
int curr = arr[i];
while (stack.empty() == false)
{
int leftEle = stack.pop();
if (leftEle < curr)
{
print (leftEle + " -- next larger element -- >" + currEle);
// This loop prints and discards all local pairs whose next larger has been found.
}
else
{
stack.push (leftEle);
break;
}
}
// current element's next larger element is yet to be seen, so current element always goes into the stack.
stack.push(curr);
}
// The elements left in the stack have no next larger element.
// Infact, the leftovers are arranged in sorted order in the stack due to this.
while (stack.empty() == false)
{
int leftoverEle = stack.pop();
print (leftoverEle + " -- next larger element -- > None");
}
}
X. Use two loops: The outer loop picks all the elements one by one. The inner loop looks for the first greater element for the element picked by outer loop. If a greater element is found then that element is printed as next, otherwise -1 is printed.
void printNGE(int arr[], int n){ int next, i, j; for (i=0; i<n; i++) { next = -1; for (j = i+1; j<n; j++) { if (arr[i] < arr[j]) { next = arr[j]; break; } } printf("%d -- %d\n", arr[i], next); }}* Link: http://www.careercup.com/question?id=6497025214382080
* Replace element of an Array with nearest bigger number at right
* side of the Array in O(n)
*
* For example if the input Array is
* 7, 5, 6, 3, 4, 1, 2, 9, 11
* output array should be
* 9, 6, 9, 4, 9, 2, 9, 11, 11
public static void replace(int[] a) {
int i=0;
// Find nearest bigger number in linear time.
// Update indices when found.
for(int j=1; j<a.length; j++) {
if(a[i] < a[j]) {
a[i] = a[j];
i++;
j = i;
}
}
// Print function for testing purposes.
for(Integer in : a) {
System.out.print(in+" ");
}
System.out.println();
}
http://www.crazyforcode.com/replace-element-next-greatest-array/
Given an array of integers, replace every element with the next greatest element on the right side in the array. Replace last element with 0 as there no element on the right side of it.
eg. if the array is {6, 7, 4, 3, 5, 2}, output {7, 5, 5, 5, 2, 0}
eg. if the array is {6, 7, 4, 3, 5, 2}, output {7, 5, 5, 5, 2, 0}
void replaceWithNextGreatest(int a[], int size) |
{ |
int maximum = a[size-1]; |
a[size-1] = 0; // last element is always replace with zero |
// Replace all other elements with the next greatest |
for(int i = size-2; i >= 0; i--) |
{ |
int temp = a[i]; |
a[i] = maximum; |
// Update the greatest element, if needed |
if(maximum < temp) |
maximum = temp; |
} |
} |
Read full article from Next Greater Element | GeeksforGeeks
