Next Greater Element II

Question

Given a circular array, for each element, find the next greater number. The next greater number is the first number you encounter going forward (looping back if needed) that is bigger than the current one.

If it doesn't exist, return -1 for that element.

Example

Input: [1, 2, 3, 2, 1]

Output: [2, 3, -1, 3, 2]

Explanation: Starting at each index, look ahead (including wrapping around) to find the first bigger number.

My Notes 📝

Create an empty stack 🧱
Loop through array twice to simulate circular structure 🔄
At each step:

If current value is greater than the top of the stack:

Pop the index
💡 Save this value as the next greater for the popped index

Push the index (only on the first round)

Two variations possible:
- 🧠 Use a result array (initialized with -1)
- 🧠 Use a map to store index → nextGreater

📌 Summary Rule of Thumb

❓ Is my key a simple integer index from 0 to n-1?
✅ Use a slice.
❓ Is my key more complex (e.g., string, timestamp, sparse ID)?
✅ Use a map.

💻 Solution 1: Using Result Array

package main

import (
    "fmt"
)

type Stack struct {
    items []int
}

func (s *Stack) Push(item int) {
    s.items = append(s.items, item)
}

func (s *Stack) Pop() int {
    popped := s.items[len(s.items)-1]
    s.items = s.items[:len(s.items)-1]
    return popped
}

func (s *Stack) Top() int {
    return s.items[len(s.items)-1]
}

func (s *Stack) Empty() bool {
    return len(s.items) == 0
}

func nextGreaterElements(nums []int) []int {
    stack := Stack{}
    n := len(nums)
    answer := make([]int, n)
    for i := range answer {
        answer[i] = -1
    }

    for i := 0; i < 2*n; i++ {
        val := nums[i % n]
        for !stack.Empty() && nums[stack.Top()] < val {
            index := stack.Pop()
            answer[index] = val
        }
        if i < n {
            stack.Push(i)
        }
    }

    return answer
}

func main() {
    result := nextGreaterElements([]int{1, 2, 3, 2, 1})
    fmt.Println(result)
}

💡 Solution 2: Using Map

package main

import (
    "fmt"
)

type Stack struct {
    items []int
}

func (s *Stack) Push(item int) {
    s.items = append(s.items, item)
}

func (s *Stack) Pop() int {
    popped := s.items[len(s.items)-1]
    s.items = s.items[:len(s.items)-1]
    return popped
}

func (s *Stack) Top() int {
    return s.items[len(s.items)-1]
}

func (s *Stack) Empty() bool {
    return len(s.items) == 0
}

func nextGreaterElements(nums []int) []int {
    stack := Stack{}
    lookup := make(map[int]int)
    n := len(nums)

    for i := 0; i < 2*n; i++ {
        val := nums[i % n]
        for !stack.Empty() && nums[stack.Top()] < val {
            index := stack.Pop()
            lookup[index] = val
        }
        if i < n {
            stack.Push(i)
        }
    }

    for i := range nums {
        if val, ok := lookup[i]; ok {
            nums[i] = val
        } else {
            nums[i] = -1
        }
    }

    return nums
}

func main() {
    result := nextGreaterElements([]int{1, 2, 3, 2, 1})
    fmt.Println(result)
}