Next Greater Element Using Stack in DSA Go - Build from Scratch

Next Greater Element Using Stack

📖 Scenario: Imagine you have a list of daily temperatures. For each day, you want to find the next day when the temperature will be higher. This helps you plan when to wear lighter clothes.

🎯 Goal: You will build a program that finds the next greater element for each number in a list using a stack. The next greater element is the first number to the right that is bigger than the current number. If there is none, we use -1.

📋 What You'll Learn

Create a slice of integers called nums with the values 2, 5, 3, 7, 1.

Create an empty slice of integers called stack to use as a stack.

Create a slice of integers called result with the same length as nums, filled with -1.

Use a for loop with index i to go through nums.

Inside the loop, use a for loop to check the top of the stack and update result when the current number is greater.

Print the result slice at the end.

💡 Why This Matters

🌍 Real World

Finding the next greater element is useful in stock price analysis, weather forecasting, and many other areas where you want to know when a higher value will occur next.

💼 Career

Understanding stack-based algorithms is important for software engineering roles, especially those involving data processing, algorithm design, and performance optimization.

1

Create the input slice

Create a slice of integers called nums with these exact values: 2, 5, 3, 7, 1.

DSA Go

# Create the input slice nums with values 2, 5, 3, 7, 1
# Your code here

Hint

Use nums := []int{2, 5, 3, 7, 1} to create the slice.

2

Setup stack and result slices

Create an empty slice of integers called stack and a slice called result with the same length as nums, filled with -1.

DSA Go

package main

func main() {
    nums := []int{2, 5, 3, 7, 1}
    // Create an empty stack slice
    // Create a result slice with length of nums filled with -1
    // Your code here
}

Hint

Use stack := []int{} and result := make([]int, len(nums)). Then fill result with -1 using a loop.

3

Find next greater elements using stack

Use a for loop with index i to go through nums. Inside it, use a for loop to check the top of stack and update result when nums[i] is greater than the element at the top index of stack. Then append i to stack.

DSA Go

package main

func main() {
    nums := []int{2, 5, 3, 7, 1}
    stack := []int{}
    result := make([]int, len(nums))
    for i := range result {
        result[i] = -1
    }
    // Loop through nums with index i
    // While stack is not empty and nums[i] > nums[stack top]
    // Update result for stack top index
    // Remove top from stack
    // Append i to stack
    // Your code here
}

Hint

Use two loops: outer for i := 0; i < len(nums); i++ and inner for len(stack) > 0 && nums[i] > nums[stack[len(stack)-1]]. Update result and pop from stack. Then push i to stack.

4

Print the result slice

Print the result slice using fmt.Println(result).

DSA Go

package main

import "fmt"

func main() {
    nums := []int{2, 5, 3, 7, 1}
    stack := []int{}
    result := make([]int, len(nums))
    for i := range result {
        result[i] = -1
    }

    for i := 0; i  0 && nums[i] > nums[stack[len(stack)-1]] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result[top] = nums[i]
        }
        stack = append(stack, i)
    }

    // Print the result slice
    // Your code here
}

Hint

Use fmt.Println(result) to print the final slice.

Practice

1. What does the Next Greater Element (NGE) problem using a stack find for each element in an array?

easy

A. The first greater element to the right of each element

B. The first smaller element to the left of each element

C. The sum of all elements greater than the current element

D. The last element in the array

Solution

1. Step 1: Understand the problem goal

   The Next Greater Element problem asks to find for each element the first element to its right that is greater than it.

2. Step 2: Recognize the stack usage

   A stack helps track elements for which we haven't found a greater element yet, efficiently finding the next greater element to the right.

3. Final Answer:

   The first greater element to the right of each element -> Option A

4. Quick Check:

   NGE = first greater element on right [OK]

Hint: Look right for first bigger number using stack [OK]

Common Mistakes:

• Confusing next greater with next smaller element
• Looking to the left instead of right
• Thinking it sums elements instead of finding one

2. Which Go code snippet correctly initializes an empty stack to use for Next Greater Element logic?

easy

A. stack := 0

B. stack := make(map[int]int)

C. stack := new(int)

D. stack := []int{}

Solution

1. Step 1: Identify stack data structure in Go

   Stacks can be implemented using slices in Go. An empty stack is an empty slice of ints: []int{}.

2. Step 2: Check other options

   stack := make(map[int]int) is a map, not a stack. stack := new(int) is a pointer to int, not a stack. stack := 0 is an int variable, not a stack.

3. Final Answer:

   stack := []int{} -> Option D

4. Quick Check:

   Stack as slice = []int{} [OK]

Hint: Use empty int slice for stack in Go [OK]

Common Mistakes:

• Using map instead of slice for stack
• Using pointer instead of slice
• Initializing stack as int variable

3. What is the output of the Next Greater Element function for the input array [4, 5, 2, 25]?

medium

A. [5, 25, 25, -1]

B. [5, -1, 25, -1]

C. [25, 25, -1, -1]

D. [-1, -1, -1, -1]

Solution

1. Step 1: Trace the array elements with stack

   For 4, next greater is 5; for 5, next greater is 25; for 2, next greater is 25; for 25, no greater element, so -1.

2. Step 2: Form the output array

   Output is [5, 25, 25, -1].

3. Final Answer:

   [5, 25, 25, -1] -> Option A

4. Quick Check:

   Next greater elements found correctly [OK]

Hint: Check each element's right side for bigger number [OK]

Common Mistakes:

• Assigning -1 too early
• Mixing up indices in output
• Ignoring last element's -1

4. Given the following Go code snippet for Next Greater Element, what is the bug?

func nextGreater(arr []int) []int {
  stack := []int{}
  result := make([]int, len(arr))
  for i := len(arr) - 1; i >= 0; i-- {
    for len(stack) > 0 && stack[len(stack)-1] <= arr[i] {
      stack = stack[:len(stack)-1]
    }
    if len(stack) == 0 {
      result[i] = 0
    } else {
      result[i] = stack[len(stack)-1]
    }
    stack = append(stack, arr[i])
  }
  return result
}

medium

A. Stack is not initialized properly

B. Loop iterates in wrong direction

C. Result uses 0 instead of -1 for no greater element

D. Comparison operator should be >= instead of <=

Solution

1. Step 1: Identify the no greater element marker

   The code assigns 0 when no greater element is found, but the standard is to use -1.

2. Step 2: Check other parts

   Stack initialization and loop direction are correct. Comparison operator <= is correct for popping smaller or equal elements.

3. Final Answer:

   Result uses 0 instead of -1 for no greater element -> Option C

4. Quick Check:

   No greater element should be -1 [OK]

Hint: Use -1 for no next greater element, not 0 [OK]

Common Mistakes:

• Returning 0 instead of -1 for no greater element
• Changing loop direction incorrectly
• Wrong comparison operator causing wrong pops

5. You have an array [13, 7, 6, 12]. Using the Next Greater Element stack approach, what is the output array?

hard

A. [ -1, -1, -1, -1 ]

B. [ -1, 12, 12, -1 ]

C. [ 12, 13, 7, -1 ]

D. [ 7, 6, 12, -1 ]

Solution

1. Step 1: Find next greater for each element

   For 13, no greater element to right, so -1. For 7, next greater is 12. For 6, next greater is 12. For 12, no greater element, so -1.

2. Step 2: Write output array

   Output is [-1, 12, 12, -1].

3. Final Answer:

   [-1, 12, 12, -1] -> Option B

4. Quick Check:

   Check right side for bigger numbers [OK]

Hint: Check each element's right side for bigger number [OK]

Common Mistakes:

• Assigning wrong next greater for 7 and 6
• Confusing output with input order
• Using 0 instead of -1 for no greater element