Find Next Greater Element

Difficulty: Medium, Asked-in: Amazon, Microsoft.

Key takeaway: An excellent problem to learn problem-solving using stack.

Let’s understand the problem

Given an array, find the Next Greater Element for every element. The Next Greater Element for an element is the first greater element on the right side of the array. Elements for which no greater element exist, consider the next greater element as -1.

Examples

Input: A[] = [3, 2, 8, 7, 9, 17, 12], Output: [8, 8, 9, 9, 17, -1, -1].

Explanation: Traversing through the array for each element, we find the next greater element on its right side, i.e., NGE of 3 is 8, NGE of 2 is 8, NGE of 8 is 9, NGE of 7 is 9, and so on.

Input: A[] = [4, 5, 2, 25, 10], Output: [5, 25, 25, -1, -1].

Discussed solution approaches

Brute force approach using nested loops
Efficient solution using stack : Traversing from left to right
Efficient solution using stack : Traversing from right to left

Brute force using nested loops

Solution idea and steps

The basic idea would be to traverse the array and find the next greater element for each element on the right side. We can use two nested loops for this.

We run an outer loop from i = 0 to n-1 to access each element X[i] and run an inner loop from j = i + 1 to n-1 to access all other elements on the right side of the current element X[i]. Inside the inner loop, we find the next greater element of the element X[i].
We use an extra array output[n] to store the next greater element for each element. When we find the next greater element for an element, we break from the inner loop and store it at output[i].
Otherwise, the inner loop will go till the end, and we won't find an element that is greater than the element X[i]. In this situation, we store -1 at output[i].
By the end of the loop, we return the array output.

Solution pseudocode

nextGreaterElement(X, n)
    create output array of size n

    for i from 0 to n - 1
        nextGreater = -1

        for j from i + 1 to n - 1
            if X[j] is greater than X[i]
                nextGreater = X[j]
                break

        output[i] = nextGreater

    return output

Time and space complexity analysis

Here outer loop runs n times, and for each iteration of the outer loop, the inner loop runs n-i-1 times. So the total number of loop iterations = n - 1 + n - 2 + .... + 1 + 1 = n(n-1)/2 + 1 = O(n^2). We are performing an O(1) operation at each loop iteration, so time complexity = O(1) * O(n^2) = O(n^2).

Efficient solution using stack: Traversing from left to right

Solution idea

Now the critical question is: how do we improve the time complexity? Is there some pattern in the problem that could help us find an efficient solution? Let's think!

Next greater elements in an array visualisation

If we look at the input array from left to right, there are two observations:

Case 1 (Decreasing sequence): If several values decrease, they may all have the same next greater element: the first value to their right that is greater than them. For example, in [6, 4, 3, 8], the next greater for 6, 4, and 3 is 8. Similarly, in [8, 7, 2, 1, 12], the next greater for each of 8, 7, 2, and 1 is 12.

Case 2 (Increasing sequence): If values increase, each value’s next greater element is the next value in the sequence. For example, in [12, 15, 16], 15 is the next greater for 12, and 16 is the next greater for 15. Similarly, in [5, 11, 13], 11 is the next greater for 5, and 13 is the next greater for 11.

One idea is to scan from left to right. When we find an element that is greater than the previous element, we record it as the next greater element of the previous element. This current element may also be the next greater element for other earlier elements (Case 1). The key question is: how do we keep track of those earlier elements? We can store them in a stack.

Solution steps

We create an empty stack s.
We also declare an array output[n] to store the next greater elements.
Now we traverse the array from left to right and push each element into the stack until the element at the top of the stack is greater than the current element. Note: We push indices instead of the elements themselves so we can identify each element’s position in the output and store its next greater element.
Once the current element is greater than the top element in the stack, we keep popping elements in a loop until the top of the stack is smaller than the current element or the stack becomes empty. During this process, we set the current element as the next greater element of all the popped elements.
Now we push the current element into the stack and repeat the above process.
Once all the elements in the array are processed, the stack may not be empty. So remaining elements in the stack do not encounter any greatest element. So we pop the elements from the stack and update their next greater element to be -1.
By the end of the above process, we return the output[].

Solution pseudocode

nextGreaterElement(X, n)
    create an empty stack s
    create output array of size n

    push index 0 onto s

    for i from 1 to n - 1
        while s is not empty and X[s.top] <= X[i]
            output[s.top] = X[i]
            pop s

        push i onto s

    while s is not empty
        output[s.top] = -1
        pop s

    return output

Time and space complexity analysis

Every element is pushed and popped at most once from the stack. So time complexity = O(n). In the worst-case scenario, the space complexity is O(n) for the stack.

Efficient solution using stack: Traversing from right to left

Solution idea

The is similar to the previous approach, but we process elements from right to left. The idea is to find the nearest element to the right of X[i] that is greater than it. So traversing from right to left helps us to keep possible answers in a stack.

As we scan from right to left, If s.top() > X[i], then top is the nearest value that is greater than X[i]. We store it as the next greater element of X[i]. Finally, we push X[i] onto the stack as a possible answer for elements farther to the left.
When we find s.top() <= X[i], we pop every element less than or equal to X[i]. None can be the next greater element: they are not greater than X[i] and X[i] is closer to the remaining elements on the left, so it makes them irrelevant. After removing these values, the top element is the nearest value that is greater than X[i]. So we store it in output[i]. If the stack is empty, no greater value exists to the right, so store -1.
Now we push X[i] onto the stack because it can be the next greater element for elements farther left.

Note: Here we are pushing values rather than their indices because each iteration already tells us the output position. So we only need the next greater value.

Solution pseudocode

nextGreaterElement(X, n)
    create an empty stack s
    create output array of size n

    for i from n - 1 down to 0
        while s is not empty and s.top <= X[i]
            pop s

        if s is not empty
            output[i] = s.top
        else
            output[i] = -1

        push X[i] onto s

    return output

Time and space complexity analysis

Every element is pushed and popped at most once to the stack. So time complexity = O(n). Space complexity in the worst case = O(n), for the stack.

Critical ideas to think!

Can we solve this problem using some other approaches?
Can we try to use other data structures other than the stack? If yes, then which one?
What will be the worst and best-case scenario of the space complexity in the stack-based approaches?
How do we modify the above approaches if the given array is circular?

Comparison of time and space complexities

Using nested loops: Time = O(n^2), Space = O(1)
Stack solution traversing from left to right: Time = O(n), Space = O(n)
Stack solution traversing from right to left: Time = O(n), Space = O(n)

Find Next Greater Element for Every Element

Let’s understand the problem

Examples

Discussed solution approaches

Brute force using nested loops

Solution idea and steps

Solution pseudocode

Time and space complexity analysis

Efficient solution using stack: Traversing from left to right

Solution idea

Solution steps

Solution pseudocode

Time and space complexity analysis

Efficient solution using stack: Traversing from right to left

Solution idea

Solution pseudocode

Time and space complexity analysis

Critical ideas to think!

Comparison of time and space complexities

Suggested coding questions to practice

More from EnjoyAlgorithms

Self-paced Courses and Blogs