Find The Next Greater Element

Introduction

 

In this article, you will learn how to find every element's next greater element.

 

Problem Statement 

 

Given an array, for each element, find the next or element's right greater element. If there is no greater element, then set the value to -1. Here is one example, array [4, 2, 5, 9, 2, 3] would result in [5, 5, 9, -1, 3, -1].

 

Approach 1

 

The most naive way to solve this problem would be by using nested loops, one over every element, and then loop over all elements to its right. If we find a greater element, then we store it and move on or else we store -1.

 

Time Complexity - O(N^2)

Space Complexity - O(1).

 

It is a pretty slow algorithm since every element potentially has to visit every element to the right. But the algorithm doesn't use any extra space. Here's a sample code in C# that demonstrates this algorithm:

class Program
{
    static void Main(string[] args)
    {
        int[] array = new int[] { 4, 2, 5, 9, 2, 3 };
        int[] result = Approach1(array);
        //result is [ 5, 5, 9, -1, 3, -1 ]
    }
    static int[] Approach1(int[] array)
    {
        int[] result = new int[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            //firstly assume the element has no next greater element
            result[i] = -1;

            //find next greater element by iterating over the rest
            for (int j = i + 1; j < array.Length; j++)
            {
                //found the next greater element
                if (array[j] > array[i])
                {
                    result[i] = array[j];
                    break;
                }
            }
        }
        return result;
    }
}

Approach 2

 

This approach needs a stack to keep the index of the elements that don't have their next greater elements. In this solution, we visit every element to check whether the value of the current element is greater than the element on the top of the stack.

 

Time Complexity - O(N)

Space Complexity - O(N).

 

It is fast because we visit each element once. In the worst case, we have to put all elements onto the stack using up a lot of extra space. A pseudocode illustrating this solution is shown below using C#:

class Program
{
    static void Main(string[] args)
    {
        int[] array = new int[] { 4, 2, 5, 9, 2, 3 };
        int[] result = Approach2(array);
        //result is [ 5, 5, 9, -1, 3, -1 ]
    }
    static int[] Approach2(int[] array)
    {
        Stack<int> nextGreaterIndex = new Stack<int>();
        int[] result = new int[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            //check if this element has any next greater element
            while (nextGreaterIndex.Count > 0)
            {
                if (array[i] > array[nextGreaterIndex.Peek()])
                {
                    result[nextGreaterIndex.Peek()] = array[i];
                    nextGreaterIndex.Pop();
                }
                else
                    break;
            }
            nextGreaterIndex.Push(i);
        }

        //all elements left will have no next greater element
        while (nextGreaterIndex.Count > 0)
        {
            result[nextGreaterIndex.Peek()] = -1;
            nextGreaterIndex.Pop();
        }
        return result;
    }
}

Approach 3

 

This solution is very similar to the above approach 2. The only difference is that we will visit the elements in reverse order. The reason is to have a greater element in the stack for the current element. The rest of with time and space complexities are the same as in approach 2. Below is a code sample for this approach in C#:  

class Program
{
    static void Main(string[] args)
    {
        int[] array = new int[] { 4, 2, 5, 9, 2, 3 };
        int[] result = Approach3(array);
        //result is [ 5, 5, 9, -1, 3, -1 ]
    }
    static int[] Approach3(int[] array)
    {
        Stack<int> nextGreaterIndex = new Stack<int>();
        int[] result = new int[array.Length];

        //reverse iteration
        for (int i = array.Length - 1; i >= 0; i--)
        {
            //pop untill the greater element
            while (nextGreaterIndex.Count > 0 && array[nextGreaterIndex.Peek()] <= array[i])
                nextGreaterIndex.Pop();

            //assign result with the top element of the stack
            result[i] = nextGreaterIndex.Count > 0 ? array[nextGreaterIndex.Peek()] : -1;

            nextGreaterIndex.Push(i);
        }
        return result;
    }
}