Next Greater Element | DSA Journal

Question

You're given two arrays: nums1 is a subset of nums2. For each element in nums1, find the next greater number in nums2 — that is, the first number to the right of it that is larger.

If no such number exists, return -1 for that element.

Example

Input:

nums1 = [2, 4]

nums2 = [1, 2, 3, 4]

Output: [3, -1]

Explanation: The next greater number after 2 in nums2 is 3. 4 has no greater number after it, so we return -1.

My Notes

Create an empty stack.
Create a dictionary to store the next greater for each number in nums2.
Iterate through nums2:

While the stack isn’t empty and the current number is greater than the top of the stack:

Pop from the stack.
Save the current number as the next greater for the number you just popped.

Push the current number onto the stack.

After the loop, whatever is still in the stack has no next greater → leave them unmapped or mapped to -1.
Build result for each number in nums1 by looking it up in the dictionary.

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 nextGreaterElement(nums1 []int, nums2 []int) []int {
    stack := Stack{}
    lookup := make(map[int]int)

    for _, item := range nums2 {
        for !stack.Empty() && stack.Top() < item {
            lookup[stack.Pop()] = item
        }
        stack.Push(item)
    }

    for i, value := range nums1 {
        if greater, ok := lookup[value]; ok {
            nums1[i] = greater
        } else {
            nums1[i] = -1
        }
    }

    return nums1
}

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