This program demonstrates how to find the next greater element for each element in an array using a stack data structure. The next greater element for an element x is the first greater element on the right side of x in the array.

Program Structure

• nextGreaterElement Function: This function uses a stack to track elements and finds the next greater element for each element in the array.
• Main Method: Demonstrates the functionality by applying the function to a sample array and printing the results.

Java Code

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

public class NextGreaterElement {
    public static int[] nextGreaterElement(int[] nums) {
        int[] result = new int[nums.length];
        Stack<Integer> stack = new Stack<>();
        Arrays.fill(result, -1); // Initialize result array with -1

        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                result[stack.pop()] = nums[i];
            }
            stack.push(i);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 2, 25};
        int[] result = nextGreaterElement(nums);
        System.out.println("Next Greater Elements: " + Arrays.toString(result));
    }
}

Explanation of How the Program Works

1. Initialization: A result array is initialized with -1, assuming that no next greater element is found.
2. Stack Usage: A stack is used to keep indexes of the array elements. The top of the stack refers to the index of the last element that has not found its next greater element.
3. Iterating Through Array: For each element, if it is greater than the element corresponding to the index at the top of the stack, that element is popped from the stack and the current element is set as its next greater element in the result array.
4. Result Compilation: After iterating through the array, the elements left in the stack are those that do not have any greater element on their right.

Key Components:

• nextGreaterElement Function: This is the core function that uses a stack to track the indices of array elements. It efficiently finds the next greater element for each element in the array.
• Main Method: It serves as the entry point for the program, providing an example array and outputting the result of applying the nextGreaterElement function.

This approach ensures that each element is processed only a few times (pushed and popped from the stack once), leading to a linear runtime complexity of O(n), which is optimal for this type of problem.

Conclusion

The next greater element problem is efficiently solved using a stack with a time complexity of O(n). This method is particularly useful for large arrays where a brute-force solution would be too slow.