Nearest / Next Greater Element to the Right of Every Element

1. Introduction

This blog post addresses a common problem in array manipulation: finding the Next Greater Element (NGE) for every element in an array. The Next Greater Element for an element x is defined as the first greater element on the right side of x in the array.

Problem

Given an array, print the Next Greater Element (NGE) for every element. For elements that have no greater element on the right, print -1.

2. Solution Steps

1. Use a stack to keep track of the elements whose NGE is not found yet.

2. Iterate through the array, and for each element:

a. Pop elements from the stack if the current element is greater than the stack's top element.

b. The current element is the NGE for all elements that are popped.

c. Push the current element onto the stack.

3. For elements remaining in the stack, their NGE is -1.

4. Return the array of NGEs.

3. Code Program

import java.util.Arrays;
import java.util.Stack;

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] input1 = {1, 3, 2, 4};
        int[] input2 = {6, 4, 12, 5, 2, 10};

        System.out.println("Next greater elements: " + Arrays.toString(findNextGreaterElements(input1)));
        System.out.println("Next greater elements: " + Arrays.toString(findNextGreaterElements(input2)));
    }

    // Method to find the next greater element for each element in the array
    public static int[] findNextGreaterElements(int[] nums) {
        int[] nge = new int[nums.length];
        Stack<Integer> stack = new Stack<>();

        for (int i = nums.length - 1; i >= 0; i--) {
            // Pop elements from the stack until the current element is smaller than the stack's top
            while (!stack.isEmpty() && nums[i] >= stack.peek()) {
                stack.pop();
            }

            // The next greater element is the top of the stack, if available
            nge[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[i]);
        }

        return nge;
    }
}

Output:

Next greater elements: [3, 4, 4, -1]
Next greater elements: [12, 12, -1, 10, 10, -1]

Explanation:

The findNextGreaterElements method uses a stack to efficiently find the next greater element for each element in the array. The stack stores elements in decreasing order from top to bottom. For each element in the array (traversed from right to left), the method pops elements from the stack until it finds an element greater than the current one. This element is the next greater element for the current array element. If the stack becomes empty, the next greater element is -1. The method correctly identifies the next greater elements for each element in the provided examples.