This program finds the next greater element for each element of a given array. The next greater element for an element x is the first greater element on the right side of x in the array. If no such element exists, the output is -1.

Program Code

package main

import (
    "fmt"
)

// nextGreaterElements finds the next greater element for each element in the given array
func nextGreaterElements(nums []int) []int {
    result := make([]int, len(nums))
    stack := []int{}

    // Initialize result array with -1
    for i := range result {
        result[i] = -1
    }

    for i, num := range nums {
        // Use the stack to keep the indices where the next greater element is not yet found
        for len(stack) > 0 && nums[stack[len(stack)-1]] < num {
            popIndex := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result[popIndex] = num
        }
        stack = append(stack, i)
    }

    return result
}

func main() {
    nums := []int{4, 5, 2, 25}
    fmt.Println("Array:", nums)
    fmt.Println("Next greater elements:", nextGreaterElements(nums))
}

Explanation

• Function Definition: The function nextGreaterElements takes an array of integers as input and returns an array of integers where each element is replaced by the next greater element.
• Algorithm:
  • Initialize the result array with `-1` for each element.
  • Use a stack to keep track of the indices for which a greater element has not yet been found.
  • Iterate through the array, and for each element, check if it can be the next greater element for the elements whose indices are in the stack.
  • Update the result for those indices accordingly and push the current index onto the stack.

Running the Program

To execute this Go program:

1. Save the code in a file named nextgreaterelement.go.
2. Open a terminal or command prompt.
3. Navigate to the directory where the file is stored.
4. Run the program by typing go run nextgreaterelement.go.

The output will display the array and the next greater elements for each element in the array, demonstrating how the stack is used to efficiently solve the problem by keeping track of the indices where the next greater element has not been found yet. Adjust the main function to test different inputs and see how the algorithm scales with different sizes and contents of arrays.