Next Greater Element in array

Problem: You are given an array, print the next greater element for each element. Elements for which no greater element exist, print next greater element as -1. You have to reduce the number of comparisons.

For any array, rightmost element always has next greater element as -1.
eg. For array [4, 15, 2, 9, 20, 11, 13] greater elements are as follows –

4 –> 15
15 –> 20
2 –> 9
20 –> -1
11 –> 13
13 –> -1

Method 1 : Brute Force O (n^2) method

Use two loops. The outer loop runs from 0 to n – 1 and one by one picks all elements from left to right. The inner loop compares the picked element to all the elements to its right side. If the picked element is greater than all the elements to its right side, then print -1.

Method 2 : Using a stack O(n) solution

Steps:

1. Take stack A.
2. Initially the stack is empty. Traverse the array from left to right. For each element.
a. if the stack is empty push the element in the stack.
b. if the stack is non empty keep on popping elements from the stack till popped element < current element.
The next greater element for every popped element would be the current element. If popped element > current element.
Push popped element and then current element on the stack.
3. When the traversal is complete, if the stack is nonempty pop elements from the stack and set the values of next greater element for these popped element as -1.

Example
for array [4, 15, 2, 9, 20, 11, 13]
stack A -> empty
1. push element 4 on stack A->4
2. pop 4 from the stack. Compare it with 15 since 4 < 15 set next greater element of 4 as 15.
A->15
3. pop 15 from the stack. 15 > 2 . Push 15 on the stack. Push 2 on the stack.
A->15->2
4. pop 2 from the stack. 2 < 9. set next greater element of 2 as 9. push 9 on the stack.
A->15->9
5. pop 9 from the stack. 9 < 20. Set next greater element of 9 as 20.
pop 15 from the stack. 15 < 20. Set next greater element of 15 as 20. Push 20 on the stack.
A-> 20
6. Pop 20 from the stack. 20 > 11. Push 20 on stack. Push 11 on stack
A->20->11
7. Pop 11 from the stack. 11 < 13. Set next greater element of 11 as 13. Push 13 on the stack.
A->20->13
8. Set the value of next greater elements for all the elements present in the stack as -1.

Implementation:


/* Basic Stack operation - Push, Pop, isEmpty have been 
left to implement for the readers */
void printNextGreater(int arr[], int n)
{
    int i = 0;
    struct stack s;
    s.top = -1;
    int element, next;

    for (i=0; i<n; i++)
    {
     /* push the first element to stack */
		if(i == 0)
		{
			push(&s, arr[0]);
			continue;
		}
		
        next = arr[i];

        if (!isEmpty(&s))
        {
            /* if stack is not empty, then pop 
            an element from stack */
            element = pop(&s);

            while (element < next)
            {
                printf("\n %d -> %d", element, next);
                if(isEmpty(&s))
                   break;
                element = pop(&s);
            }

            /* If element is greater than next, 
            then push the element back */
            if (element > next)
                push(&s, element);
        }

        /* push next to stack so that we can 
        find next greater for it */
        push(&s, next);
    }
    
    while (!isEmpty(&s))
    {
        element = pop(&s);
        next = -1;
        printf("\n %d -> %d", element, next);
    }
}

Time Complexity: O(n). The worst case occurs when all elements are sorted in decreasing order. If elements are sorted in decreasing order, then every element is processed at most 4 times.

One Thought on “Next Greater Element in array

  1. You forgot to mention 9->20 in the example above.

    Also , how is this solution O(n) ?

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation