Logo
All Questions

Efficiently find the next greatest element in an array.

DifficultyalgorithmsAsked at Meta (Facebook)

Question Explain

In this question, you are required to find and return the next greater element for each element in an array. To be precise, if an array is like [4,5,2,25], the next greater element for 2 is 5 and for 5 is 25. Since there isn't any element greater than 25 in the array, it would return -1 for 25. This requires you to have a comprehensive understanding of how arrays work as well as skills in applying algorithmic thinking.

A recommended approach to solve this problem can be through use of a stack data structure. The main idea is to push an element to the stack and for each subsequent element, if it's greater than the top item of the stack, this means it's the next greater element for the elements in stack up to this point. So, we keep popping elements from the stack until we find an element greater in the stack or stack becomes empty. Push this new element to stack.

Answer Example 1

Here is an example in Python language,

def nextGreaterElement(array):
    stack = []
    result = [-1] * len(array)

    for i in range(len(array)):
        while stack and array[i] > array[stack[-1]]:
            result[stack.pop()] = array[i]
        stack.append(i)

    return result

In this solution, we create a stack and an array of -1s for the final result. We iterate over the given array. For each item, we check if stack is not empty and if current array item is greater than the top item in stack. As long as this condition is true, this means that the current array item is the next greater item for element at index stack[-1]. Hence, we pop the top index from stack and set result for this index to current array item. We add the current index to stack regardless. The final result array will hold the next greater elements for all items in given array.

Answer Example 2

Here is another example in Java language,

public void nextGreaterElement(int[] array) {
    Stack<Integer> stack = new Stack<>();
    int[] result = new int[array.length];
  
    for (int i = array.length - 1; i >= 0; i--) {
        while (!stack.isEmpty() && stack.peek() <= array[i]) {
            stack.pop();
        }
  
        if (!stack.isEmpty()) {
            result[i] = stack.peek();
        } else {
            result[i] = -1;
        }

        stack.push(array[i]);
    }
}

In this solution, we follow a similar approach but iterate from the end of array. For each item, we keep popping from stack until we find an item greater than current array item or until stack becomes empty. If stack is not empty, this means that the top item in stack is the next greater element for current array item. If stack is empty, there is no next greater element. We push the current array item to stack, regardless. The loop continues for rest of the items in array.

More Questions

Question Quick Reference by Category: