Next Greater Element

Next Greater Element

LeetCode 496 - Next Greater Element I
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.

Element       NGE
   4      -->   5
   5      -->   25
   2      -->   25
   25     -->   -1

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

Time Complexity is O(n) because each element is pushed 1 time and popped 1 time from the stack.
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);

        }

    }

http://codingloverlavi.blogspot.com/2014/11/next-greater-element.html

    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

    public static void printNGE() 

    {

        Stack<Integer> s = new Stack<>();

        int nge[] = new int[arr.length];

  

        // iterate for rest of the elements 

        for (int i = arr.length - 1; i >= 0; i--) {

              

            /* if stack is not empty, then 

            pop an element from stack. 

            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 */

            if (!s.empty()) {

                while (!s.empty() && s.peek() <= arr[i]) {

                    s.pop();

                }

            }

            nge[i] = s.empty() ? -1 : s.peek();

            s.push(arr[i]);

  

        }

        for(int i = 0; i < arr.length; i++) 

        System.out.println(arr[i] + " --> " + nge[i]);

    }

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");
    }
}

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

    }

}

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/

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}

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;

}

}

Related: Replace every element with the next greatest
Read full article from Next Greater Element | GeeksforGeeks