Next Greater Element Using Stack in DSA Go - Execution Trace

Concept Flow - Next Greater Element Using Stack

Start with empty stack

↓

Iterate over array elements

↓

While stack not empty and current element > top of stack

↓

Pop from stack

↓

Assign current element as next greater

↓

Push current element index onto stack

↓

Repeat for all elements

↓

For remaining indices in stack

↓

Assign -1 as no next greater element

↓

End

We scan the array left to right, using a stack to keep indexes of elements waiting for their next greater element. When a bigger element appears, we pop smaller ones and assign their next greater.

Execution Sample

DSA Go

arr := []int{4, 5, 2, 25}
stack := []int{}
result := make([]int, len(arr))
for i := 0; i < len(arr); i++ {
  for len(stack) > 0 && arr[i] > arr[stack[len(stack)-1]] {
    idx := stack[len(stack)-1]
    stack = stack[:len(stack)-1]
    result[idx] = arr[i]
  }
  stack = append(stack, i)
}
for len(stack) > 0 {
  idx := stack[len(stack)-1]
  stack = stack[:len(stack)-1]
  result[idx] = -1
}

This code finds the next greater element for each item in the array using a stack to track indexes.

Execution Table

Step	Operation	Current Index (i)	Stack (indexes)	Result Array	Visual State
1	Start	-	[]	[-1, -1, -1, -1]	Stack empty, result initialized with -1
2	Process element 4	0	[0]	[-1, -1, -1, -1]	Push index 0 (value 4)
3	Process element 5	1	[1]	[5, -1, -1, -1]	5 > 4, pop 0, set result[0]=5, push 1
4	Process element 2	2	[1, 2]	[5, -1, -1, -1]	2 < 5, push 2
5	Process element 25	3	[3]	[5, 25, 25, -1]	25 > 2 pop 2 set result[2]=25; 25 > 5 pop 1 set result[1]=25; push 3
6	End	-	[]	[5, 25, 25, -1]	No next greater for index 3, set result[3] = -1

💡 All elements processed; remaining stack indexes have no next greater element, so result remains -1 for them.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
i	-	0	1	2	3	-	-
stack	[]	[0]	[1]	[1,2]	[3]	[]	[]
result	[-1,-1,-1,-1]	[-1,-1,-1,-1]	[5,-1,-1,-1]	[5,-1,-1,-1]	[5,25,25,-1]	[5,25,25,-1]	[5,25,25,-1]

Key Moments - 3 Insights

Why do we pop from the stack only when current element is greater than the element at stack's top index?

Because the stack stores indexes of elements waiting for their next greater element. When current element is greater, it means we found the next greater for those smaller elements. This is shown in steps 3 and 5 where popping happens only if arr[i] > arr[stack top].

Why do we push the current index onto the stack after popping?

We push current index because it might have a next greater element later. Even if we popped smaller elements, current element still waits for its next greater. This is visible in steps 2, 3, 4, and 5 where after popping, current index is pushed.

Why do some elements in the result remain -1 after processing all elements?

Because those elements have no next greater element to their right. The stack keeps their indexes till the end, and we leave their result as -1. Step 6 shows index 3 remains with -1.

Visual Quiz - 3 Questions

Look at the execution table at Step 3. What is the content of the stack after processing element 5?

A [1]

B [0,1]

C []

D [2]

💡 Hint

Check the 'Stack (indexes)' column at Step 3 in the execution table.

At which step does the result for index 2 get assigned a next greater element?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Result Array' column and see when result[2] changes from -1.

If the input array was [4, 3, 2, 1], what would be the final result array?

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

B [3, 2, 1, -1]

C [4, 4, 4, -1]

D [5, 5, 5, -1]

💡 Hint

Since no element has a greater element to its right, all remain -1 as per the logic in the execution table.

Concept Snapshot

Next Greater Element Using Stack:
- Use a stack to store indexes of elements waiting for next greater.
- Iterate array left to right.
- While current element > element at stack top, pop and assign next greater.
- Push current index onto stack.
- Remaining stack indexes get -1 (no next greater).
- Time complexity: O(n) because each element is pushed and popped once.

Full Transcript

This concept shows how to find the next greater element for each item in an array using a stack. We start with an empty stack and an output array initialized with -1. We scan the array from left to right. For each element, we check if it is greater than the element at the top index of the stack. If yes, we pop that index from the stack and assign the current element as its next greater. We repeat this until the stack is empty or the current element is not greater. Then we push the current index onto the stack. After processing all elements, any indexes left in the stack have no next greater element, so their result remains -1. This method efficiently finds next greater elements in one pass with O(n) time. The execution table traces each step with stack content and result array updates. Key moments clarify why we pop only when current element is greater, why we push current index, and why some results remain -1. The visual quiz tests understanding of stack state and result assignments at specific steps.

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