Next Greater Element 🎯

Welcome to our lesson on the Next Greater Element! This concept is a crucial part of Data Structures and Algorithms, and it will help you understand how to find the next greater element for a given element in an array. Let's dive in!

What is the Next Greater Element? 📝

The Next Greater Element (NGE) for a given element in an array is the first greater element on the right side of the array. If there's no greater element, the Next Greater Element is -1.

Here's an example:

python

# Example array
arr = [4, 5, 2, 25, 20, 15, 16, 20, 12, 14]

# NGE for each element
nge = []
stack = []

# Iterate through the array
for i in range(len(arr)):
    # If the top of the stack is greater than the current element, we have found the NGE
    while stack and stack[-1] > arr[i]:
        top_element = stack.pop()
        nge.append(top_element)

    # If the top of the stack is less than or equal to the current element, we push it onto the stack
    if stack:
        stack.append(arr[i])

    # When the loop finishes, the remaining elements in the stack are the Next Greater Elements
    nge += [top_element for top_element in stack[::-1]]

print("Next Greater Elements:", nge)

Output: [2, 25, 16, 20, -1, 16, 14, -1, -1, -1]

Why does the algorithm work? 💡

The algorithm works by maintaining a stack to keep track of the elements we've seen. When we encounter a new element, we first check if the top of the stack is greater than the current element. If it is, we have found the Next Greater Element, so we pop it off the stack and add it to our result.

If the top of the stack is not greater, we push the current element onto the stack and continue iterating. When we've finished iterating through the array, the remaining elements in the stack are the Next Greater Elements for the elements we have not yet found a greater element.

Practice Time 📝

Now it's your turn! Try solving the following problems related to the Next Greater Element:

That's it for today! Keep practicing and you'll master the Next Greater Element in no time. Happy coding! ✅