Python - Next Greater Element in an Array (NGE)

Problem Statement

Given an array, find the Next Greater Element (NGE) for every element. The NGE for an element is the first greater element on the right. If no greater element exists, return -1.

Example 1

Input: [4, 5, 2, 10]  

Output: [5, 10, 10, -1]

Explanation:

The next greater element for 4 is 5.

The next greater element for 5 is 10.

The next greater element for 2 is 10.

No greater element exists for 10, so -1.

Brute Force Approach (O(N²))

For each element, iterate through the remaining elements to find the next greater one.

def next_greater_element(arr):

    n = len(arr)

    result = [-1] * n

    for i in range(n):

        for j in range(i + 1, n):

            if arr[j] > arr[i]:

                result[i] = arr[j]

                break               

    return result

# Example

print(next_greater_element([4, 5, 2, 10]))  # Output: [5, 10, 10, -1]

print(next_greater_element([3, 7, 1, 8, 2]))  # Output: [7, 8, 8, -1, -1]