To watch the youtube video going over this topic, please click here.
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.
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.)
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.
There are possibly optimizations, regardless of the algorithm chosen:
Edge cases to cover:
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.
Hi, I'm srcmake. I play video games and develop software.
Pro-tip: Click the "DIRECTORY" button in the menu to find a list of blog posts.
License: All code and instructions are provided under the MIT License.