Next Greater Element Using Stack in DSA Go

Mental Model

We find the next bigger number for each element by looking ahead using a stack to remember numbers waiting for their bigger neighbor.

Analogy: Imagine standing in a line of people with different heights. For each person, you want to find the next taller person standing to their right. You keep track of people who haven't found a taller person yet by stacking them up.

Array: [4] [5] [2] [25] [7] [8]
Stack: empty
Result: [-1] [-1] [-1] [-1] [-1] [-1]

Dry Run Walkthrough

Input: array: [4, 5, 2, 25, 7, 8]

Goal: Find the next greater element for each number in the array

Step 1: Push 4 to stack

Stack: [4]
Result: [-1, -1, -1, -1, -1, -1]

Why: Start with first element, no next greater found yet

Step 2: 5 is greater than top of stack (4), pop 4 and set result[0] = 5; push 5

Stack: [5]
Result: [5, -1, -1, -1, -1, -1]

Why: 5 is next greater for 4, update result and keep 5 for next comparisons

Step 3: 2 is not greater than top of stack (5), push 2

Stack: [5, 2]
Result: [5, -1, -1, -1, -1, -1]

Why: 2 waits for a bigger number to its right

Step 4: 25 is greater than top of stack (2), pop 2 and set result[2] = 25; also greater than 5, pop 5 and set result[1] = 25; push 25

Stack: [25]
Result: [5, 25, 25, -1, -1, -1]

Why: 25 is next greater for 2 and 5, update both results

Step 5: 7 is not greater than top of stack (25), push 7

Stack: [25, 7]
Result: [5, 25, 25, -1, -1, -1]

Why: 7 waits for a bigger number

Step 6: 8 is greater than top of stack (7), pop 7 and set result[4] = 8; push 8

Stack: [25, 8]
Result: [5, 25, 25, -1, 8, -1]

Why: 8 is next greater for 7

Step 7: No more elements, pop remaining stack elements (25, 8) and set their results to -1

Stack: empty
Result: [5, 25, 25, -1, 8, -1]

Why: No next greater elements for 25 and 8

Result:

Result array: [5, 25, 25, -1, 8, -1]

Annotated Code

DSA Go

package main

import "fmt"

func nextGreaterElement(arr []int) []int {
	result := make([]int, len(arr))
	for i := range result {
		result[i] = -1 // default -1 for no greater element
	}
	stack := []int{} // stack holds indices

	for i, val := range arr {
		// while current val is greater than val at stack top index
		for len(stack) > 0 && val > arr[stack[len(stack)-1]] {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1] // pop
			result[top] = val // set next greater
		}
		stack = append(stack, i) // push current index
	}

	// remaining indices have no next greater, already -1
	return result
}

func main() {
	arr := []int{4, 5, 2, 25, 7, 8}
	res := nextGreaterElement(arr)
	fmt.Println(res)
}

for i := range result { result[i] = -1 // default -1 for no greater element }

initialize result with -1 meaning no next greater found yet

for i, val := range arr {

iterate over each element to find next greater

for len(stack) > 0 && val > arr[stack[len(stack)-1]] {

while current value is greater than value at top of stack, pop and update result

top := stack[len(stack)-1] stack = stack[:len(stack)-1] result[top] = val

pop index from stack and set its next greater element

stack = append(stack, i)

push current index to stack to find its next greater later

Output

[5 25 25 -1 8 -1]

Complexity Analysis

Time: O(n) because each element is pushed and popped at most once from the stack

Space: O(n) for the stack and result array to store indices and answers

vs Alternative: Naive approach is O(n^2) by checking each element's right side; stack reduces it to O(n)

Edge Cases

empty array

returns empty result array immediately

DSA Go

for i, val := range arr {

all elements equal

no next greater elements found, all results remain -1

DSA Go

for len(stack) > 0 && val > arr[stack[len(stack)-1]] {

strictly decreasing array

no next greater elements, all results -1

DSA Go

for len(stack) > 0 && val > arr[stack[len(stack)-1]] {

When to Use This Pattern

When you need to find the next bigger number for each element in a list efficiently, use the stack pattern to remember waiting elements and update them as you find bigger numbers.

Common Mistakes

Mistake: Pushing values instead of indices onto the stack, making it hard to update the result array correctly.
Fix: Push indices onto the stack so you can update the result array at the correct position.

Mistake: Not initializing the result array with -1, leading to incorrect default values.
Fix: Initialize the result array with -1 to indicate no next greater element found.

Summary

Finds the next greater element for each item in an array using a stack.

Use when you want to quickly find the next bigger number to the right for each element.

Keep indices of elements waiting for a bigger number on a stack and update results as you find bigger elements.

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