Next Greater Element (NGE) for Every Element of Array.

Given an array nums[] of distinct integers, find the next greater element for each element in the array. The next greater element is the first greater element to its right. If no such element exists, consider it as -1. Write a function to return an array containing the next greater elements in the input array.

Example:

Input: [3, 1, 4, 2]

Output: [4, 4, -1, -1]

Explanation:

- For element 3, the next greater element is 4.

- For element 1, the next greater element is 4.

- For element 4, there is no next greater element to its right, so it is -1.

- For element 2, there is no next greater element to its right, so it is -1.

Input: [4, 5, 2, 10, 8]

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

Explanation:

- For element 4, the next greater element is 5.

- For element 5, the next greater element is 10.

- For element 2, the next greater element is 10.

- For element 10, there is no next greater element to its right, so it is -1.

- For element 8, there is no next greater element to its right, so it is -1.

This is one of the popular stack-based problems that has been asked in many interviews and here we will understand how to approach this problem starting with a brute force solution and then optimizing it using the stack data structure.

There are multiple ways of asking this same question in an interview and if you understand the solution to this one question I can guarantee that you will be able to solve the other similar kind of questions. These questions are:

Next Greater Element to its right.
Next Smaller Element to its right.
Next Greater Element to its left.
Next Smaller Element to its left.

Brute Force Approach to Find NGE to Right.

The brute force approach is quite simple for this question, using two nested loops. The outer loop will traverse the given input array and the inner will find the next greater element to the right side of the current index.

Algorithm Steps:

Iterate through each element in the array.
For each element, iterate through the elements to its right.
Find the first element greater than the current element.
If found, set it as the next greater element. If not found, set it as -1.
Continue this process for each element in the array.

Below is the code implementation of the above approach:

C++ Java Python C#

// CPP program to find next greater element
#include<iostream>
#include<vector>
using namespace std;

// function to find next greater element
vector<int> nextGreaterElement(vector<int> nums) {
    int n = nums.size();
    vector<int> result(n, -1);

    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++){
            if(nums[j] > nums[i]){
                result[i] = nums[j];
                break;
            }
        }
    }
    return result;
}
int main() {
    vector<int> nums = {4, 5, 2, 10, 8};

    vector<int> result = nextGreaterElement(nums);

    cout << "Input Array: ";
    for(int num:nums){
        cout << num << " ";
    }

    cout << "\nNext Greater Elements to Right: ";
    for(int num:result){
        cout << num << " ";
    }

    return 0;
}

// Java code to find next greater element
import java.util.Arrays;

public class NextGreaterElement {
    public static int[] nextGreaterElement(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[j] > nums[i]) {
                    result[i] = nums[j];
                    break;
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 2, 10, 8};
        int[] result = nextGreaterElement(nums);

        System.out.print("Input Array: ");
        for (int num : nums) {
            System.out.print(num + " ");
        }

        System.out.println("\nNext Greater Elements to Right: " + Arrays.toString(result));
    }
}

# Python code to find next greater element
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n

for i in range(n):
    for j in range(i + 1, n):
        if nums[j] > nums[i]:
            result[i] = nums[j]
            break

return result

nums = [4, 5, 2, 10, 8]
result = nextGreaterElement(nums)

print("Input Array:", nums)
print("Next Greater Elements to Right:", result)

// C# code to find next greater element
using System;

class Program {
    static int[] NextGreaterElement(int[] nums) {
        int n = nums.Length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = -1;
            for (int j = i + 1; j < n; j++) {
                if (nums[j] > nums[i]) {
                    result[i] = nums[j];
                    break;
                }
            }
        }
        return result;
    }

    static void Main() {
        int[] nums = {4, 5, 2, 10, 8};
        int[] result = NextGreaterElement(nums);

        Console.Write("Input Array: ");
        foreach (int num in nums) {
            Console.Write(num + " ");
        }

        Console.WriteLine("\nNext Greater Elements to Right: " + string.Join(" ", result));
    }
}

Output:

Input Array: 4 5 2 10 8 
Next Greater Elements to Right: 5 10 10 -1 -1

Time Complexity: O(n^2) as we have used two nested loops to solve this problem.
Space Complexity: O(1) we have not used any extra space.

Next Greater Element Using Stack.

The efficient way of solving this problem is by using a stack data structure. The stack helps keep track of potential candidates for the next greater element. Let's follow the algorithm steps given below to understand this approach in detail.