[Interview Question] Finding The Next Greater Element In An Array

To watch the youtube video going over this topic, please click here.

Problem Statement

Given an array, for each element find the next greater element (to the element's right). If there is no greater element then the value is -1.

The next greater element.

---

Approach 1: O(N^2) Time | O(1) Space - For Each Element, Look Right

The naive approach is pretty simple and uses nested loops. For each element of the array, look to the elements to its right. If we find a greater element, cool. If not (and we've looked at every element to the right), then the next greater element is -1.

Here's some pseudocode that demonstrates this algorithm.

The time complexity is O(N^2) since every element potentially has to visit every element to its right.
The space complexity is O(1) since we don't use any extra space.

---

Approach 2 (Best): O(N) Time | O(N) Space - Use A Stack

One way to solve the problem is with a stack. 

The stack stores the index of elements that don't have their NGEs yet.

Every time we visit an element, we check if is value is greater than the element on top of the stack.

The following picture shows the setup we need to use a stack to find the NGE of each element in the array. We'll go through that particular example in the video. (So watch the video if you want to see how it works.)

An array, and an empty stack. (Along with the empty array which needs to be filled with the next greater element.)

The following pseudocode demonstrates the algorithm.

The time complexity is O(N) since we visit each element only once.
The space complexity is O(N) since at worst we have to put all elements onto the stack.

The source code of a working implementation (written in C++) can be found on github here.

---

Optimizations

There are possibly optimizations, regardless of the algorithm chosen:

• We can calculate the NGE array in-place, by modifying the existing array instead of creating a new one for our answers.

---

Edge Cases

Edge cases to cover:

• An empty array.

---

---

​Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels. 

Twitter: @srcmake
Discord: srcmake#3644
Youtube: srcmake
Twitch: www.twitch.tv/srcmake
​Github: srcmake

Resources
1. https://www.geeksforgeeks.org/next-greater-element/