Make delicious recipes!

Next largest element for each element


Problem: Given an unsorted array, print the nearest larger element for each element.
Nearest here refers to the distance between the indexes of two elements, not the value of the two elements.


Example: Given array [5, 9, 3, 5, 4]
The solution should print:
5 --nearest largest element-- > 9
9 --nearest largest element-- > None
3 --nearest largest element-- > 5 (NOT 4)
5 --nearest largest element-- > None
4 --nearest largest element-- > None

Solution: O(n2) is trivial to implement using two loops - outer loop iterating over all elements of the array and inner loop finding the nearest larger element in the remaining array from current index to end of array.

An O(n) solution can be implemented if we consider the following property of the problem:
By definition of the problem, we only need to consider elements towards the right of an element for finding the next larger element.
If instead of finding next larger element towards the right side of every element, we print (and discard) those elements whose next larger element is the current element, then we can find a better solution.
This approach is more efficient, because at every step, some of the elements are getting discarded.


We use a stack to store elements towards the left side of current elements which could not be discarded (because their next larger element has not come yet).
This can be called as a Decreasing Stack


Code:

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







Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal