This program determines the next greater element for each element in an array. The next greater element for an element x is the first greater element on its right. If no such element exists, the result is -1.

Program Structure

The algorithm uses a stack to keep track of elements for which we have not yet found the next greater element. As we iterate through the array:

• We push each element’s index onto the stack.
• For each new element, we check if it is greater than the element represented by the index at the top of the stack.
• If it is, we pop the stack and set the current element as the next greater element for the popped index.
• This process is repeated until the stack is empty or the current element is not greater than the element corresponding to the index at the top of the stack.
• If the stack still contains indices at the end of the iteration, these elements do not have a greater next element and are set to -1.

Python Code

def find_next_greater(arr):
    result = [-1] * len(arr)
    stack = []
    for i in range(len(arr)):
        while stack and arr[stack[-1]] < arr[i]:
            result[stack.pop()] = arr[i]
        stack.append(i)
    return result

# Example Usage
input_array = [4, 5, 2, 25]
print("Next greater elements:", find_next_greater(input_array))

Explanation of the Code

• find_next_greater function: Initializes an array of the same length as the input array with all values set to -1. This array will store the result.
• Stack operation: Uses a stack to hold indices of the array elements. The stack helps track elements for which the next greater element has not yet been found.
• Checking and updating the result: For each element, if it is greater than the element at the index at the top of the stack, update the result for that index and pop the stack.
• Final result: After iterating through the array, any remaining indices in the stack are set to -1, as no greater element exists for them.

Usage

This function can be used in contexts where it is necessary to know future trends or requirements immediately following certain data points, such as in stock price analysis, temperature readings, etc.